Algorithms & Big-O
Two programs can produce the same answer while one finishes instantly and the other never finishes at all. Big-O notation is how computer scientists describe that difference: it captures how an algorithm’s running time grows as the input grows, ignoring the details that do not scale. Once you can look at a loop and say “that is O(n)” or spot that a search is O(log n), you can reason about performance before you ever run the code. This final set makes the common complexities and classic algorithms automatic.
Practice this set for free — no account needed. Loads 14 flashcards into the learner. The learner asks it as shown here: phrase first, meaning second.
Practice in the free learnerHow to study this set
Anchor each complexity to a concrete example: O(1) is an array index, O(n) is a single loop, O(n²) is a nested loop, O(log n) is binary search. Rank them from fastest to slowest and be able to say why O(n log n) beats O(n²) for large inputs — that comparison is the one interviews love.
All 14 flashcards
Swap question and answerHow an algorithm’s running time (or memory use) grows as the input size grows — its worst-case upper bound
What does Big-O notation describe?
The running time does not depend on the input size
What is O(1) — constant time?
Example: accessing an array element by its index.
The running time grows in direct proportion to the input size
What is O(n) — linear time?
Example: scanning every element of a list once.
The running time grows with the square of the input size
What is O(n²) — quadratic time?
Typical of algorithms with a loop nested inside another loop.
The running time grows very slowly as the input grows — each step discards a large fraction of the data
What is O(log n) — logarithmic time?
Example: binary search.
O(log n)
What is the time complexity of binary search?
It works only on a sorted collection.
O(n)
What is the time complexity of linear search?
O(n log n)
What is the average time complexity of efficient sorts like merge sort?
The input must be sorted
What does binary search require of its input?
A technique where a function calls itself to solve smaller instances of the same problem
What is recursion?
The condition that stops the recursion from continuing
What is the “base case” in a recursive function?
O(n log n)
For large inputs, which is faster: an O(n log n) or an O(n²) algorithm?
O(n)
What is the time complexity of searching an unsorted array?
With no order to exploit, you may have to check every element.
How the number of operations an algorithm performs grows with the input size — not the wall-clock time on a particular machine
What does “time complexity” measure?
What to learn next
That completes the Computer Science path — basics, data structures, and algorithmic thinking. Keep all three decks in your review rotation so the complexities stay instant, and explore the other subjects to keep learning.