Theory
Time complexity describes how the running time of an algorithm grows as the input size increases. Space complexity describes how much additional memory an algorithm needs. Big O notation is commonly used to describe algorithm efficiency. Common complexities include O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ).
Example
// O(n) example
const numbers = [1, 2, 3, 4, 5];
for (const number of numbers) {
console.log(number);
}
Expected Output
Every element is visited once, so the time complexity is O(n).
Practice
Write a program that searches for a number inside an array and think about its time complexity.
Interview Questions
- What is Big O notation?
- What is the difference between time and space complexity?
- What is the time complexity of a single loop?
- What is O(1)?