8. SPACE COMPLEXITY

Question 1

What is space complexity ?

Answer 1

The complexity of computational problems in terms of the amount of space, or memory, that they require.

Question 2

We typically estimate the space complexity of Turing machines by using?

Answer 2

asymptotic notation.

Question 3

Savitch’s theorem is one of the earliest results concerning space complexity. What does it show ?

Answer 3

It shows that deterministic machines can simulate nondeterministic machines by using a surprisingly small amount of space.

Question 4

What are sublinear space bounds?

Answer 4

In sublinear space complexity, the machine is able to read the entire input but it doesn’t have enough space to store the input.

Question 5

Sublinear space algorithms allow what?

Answer 5

Sublinear space algorithms allow the computer to manipulate the data without storing all of it in main memory.

Question 6

What is L ?

Answer 6

L is the class of languages that are decidable in logarithmic space
on a deterministic Turing machine. In other words,
L = SPACE(log n).

Question 7

What is NL ?

Answer 7

NL is the class of languages that are decidable in logarithmic space on a nondeterministic Turing machine. In other words,
NL = NSPACE(log n).