Theoretical CS

3.1 Time and Space Complexity

We’ve now written many programs and functions. So far we’ve mainly been concerned with whether our code works, but how can we start analyzing how well our code works?

Computational Cost

When we think about computational cost, we are usually concerned with either how quickly the computation is accomplished (time), or how much memory the computation needs (space). We will examine examples of how to get these measures.

Big O

We can look at the upper and lower bounds for the time and space costs of an algorithm to give us some estimate of how it performs compared to other algorithms. We are also interested in how well the algorithm scales with regard to the amount of input that it takes. Rather than looking at exact counts, we can look at orders of magnitude; for example, will this loop run 10, 100 times or 100000 times?

<< 2.3 Lab 2 3.2 Recursion and Induction >>