CSC 341 (Fall 2021)

Reading: Sublinear Space Compelxity

Today, we’ll look at sublinear space complexity, the classes \(\mathsf{L}\) and \(\mathsf{NL}\). Curiously enough, we must adjust our model of computation slightly to be able to accurately capture what we mean by “less than linear space.”