Data structures and algorithms · Lesson 26 of 60 · Concept lesson · Optional
Algorithmic complexity
Big O describes how the time or memory a program needs grows as its input gets bigger.
O(1) stays the same, O(n) grows in step with the input, and O(n squared) grows much faster, such as a loop inside a loop.
Time is how many steps a program takes, and space is how much extra memory it uses.
Picture it
Code example
const numbers = [1, 2, 3];
let steps = 0;
for (const a of numbers) {
steps += 1; // one pass: O(n)
}
for (const a of numbers) {
for (const b of numbers) {
steps += 1; // a pass inside a pass: O(n squared)
}
}
console.log(steps);Output: 12
With three items, the single loop takes 3 steps and the nested loops take 9, 12 in all. With a thousand items it would be 1,000 and 1,000,000.
numbers = [1, 2, 3]
steps = 0
for a in numbers:
steps += 1 # one pass: O(n)
for a in numbers:
for b in numbers:
steps += 1 # a pass inside a pass: O(n squared)
print(steps)Output: 12
With three items, the single loop takes 3 steps and the nested loops take 9, 12 in all. With a thousand items it would be 1,000 and 1,000,000.
Check yourself
Pick an answer for each question. You can retry as many times as you like.
Loading the questions…