Time & Space Complexity

Big O notation is used to describe both time complexity and space complexity:

• Time complexity (using Big O) tells us how the running time of an algorithm increases as the input gets bigger.
• Space complexity (using Big O) tells us how the memory usage of an algorithm increases as the input gets bigger.

Note

So, Big O is the language we use to talk about both how fast an algorithm is and how much memory it uses. For example, an algorithm can have O(n) time complexity (runs in linear time) and O(1) space complexity (uses constant memory).

Time Complexity

Time complexity tells us how long an algorithm takes to run as the input gets bigger. It helps us understand if our code will still be fast when working with large amounts of data.

• Lower time complexity means faster code for big inputs.

Why is it important?

• It helps you pick the best algorithm for the job.
• It shows how your code will scale as data grows.

Example

• If you loop through a list of 10 items, it takes about 10 steps. If the list has 1,000 items, it takes about 1,000 steps. This is O(n) time.
• If you always do the same number of steps, no matter how big the input is, that’s O(1) time.

Space Complexity

What is Space Complexity?

Space complexity tells us how much extra memory (RAM) an algorithm needs as the input gets bigger. This includes variables, data structures, and function call stacks.

• Lower space complexity means your code uses less memory and can handle bigger problems.

Why is it important?

• It helps you avoid running out of memory.
• It shows if your code is efficient with resources.

Example

• If you only use a few variables, no matter how big the input is, that’s O(1) space.
• If you make a new list as big as the input, that’s O(n) space.