Complexity & Big-O
Board exams ask how fast an algorithm grows, not how many seconds your laptop took. Learn Big-O with charts you can step through, then use it to compare sorts and searches.
- Describe why algorithm cost is measured in growth, not seconds
- Read the common complexity classes and rank them
- Identify the worst case of a simple loop
Cost at a glance
- constant
- O(1)
- logarithmic
- O(log n)
- linear
- O(n)
- quadratic
- O(n²)
Topic contents
Lesson 1 of 2
Why not just time it?
A stopwatch measures your laptop, not your algorithm. Run the same code on a faster machine and the number changes, even though the steps did not. So instead of timing, we measure how the work grows as the input grows.
That is the whole idea behind Big-O notation. It answers one question: if I double the input, roughly what happens to the work? If the work doubles, that is linear, O(n). If it stays flat, that is constant, O(1). If it barely moves, that is logarithmic, O(log n).
Picture a class register with ten names versus twenty. Scanning every name to find one student doubles the checks. That is O(n). Jumping straight to row five in a printed list is O(1). Board questions often ask you to name which pattern you see.
Lesson 2 of 2
The classes you will actually meet
O(1) constant: reading array[5]. The array does not care how long it is; you jump straight there.
O(log n) logarithmic: searching a balanced binary search tree. Each comparison throws away half of what is left.
O(n) linear: scanning a list for a value. In the worst case you look at every element.
O(n log n): the good sorting algorithms, like merge sort.
O(n²) quadratic: a loop inside a loop, like bubble sort. Double the input and the work goes up four times, which hurts on big school datasets and real apps alike.
Worked examples
Read the code, then change it
Copy any example into the playground and break it on purpose. That is the fastest way to learn what each line is holding up.
function findIndex(values, target) {
for (let i = 0; i < values.length; i++) {
if (values[i] === target) return i; // best case: first element
}
return -1; // worst case: we checked all n elements
}
console.log(findIndex([10, 20, 30, 40], 30));Practice
Work these out yourself
No answer key here on purpose: these are the questions worth thinking through before you move on. Open one and work it out.
0/3 attemptedAssessment
Check your understanding
Answer each question, then read the explanation. That is where the learning is.
Finished this topic?
0 of 2 lessons marked done. Marking the topic complete ticks the rest.