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.
Time Complexity
Section titled “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?
Section titled “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
Section titled “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
Section titled “Space Complexity”What is Space Complexity?
Section titled “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?
Section titled “Why is it important?”- It helps you avoid running out of memory.
- It shows if your code is efficient with resources.
Example
Section titled “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.