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.
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
What does Big-O notation describe?
How an algorithm’s running time (or memory use) grows as the input size grows — its worst-case upper bound
What is O(1) — constant time?
The running time does not depend on the input size
Example: accessing an array element by its index.
What is O(n) — linear time?
The running time grows in direct proportion to the input size
Example: scanning every element of a list once.
What is O(n²) — quadratic time?
The running time grows with the square of the input size
Typical of algorithms with a loop nested inside another loop.
What is O(log n) — logarithmic time?
The running time grows very slowly as the input grows — each step discards a large fraction of the data
Example: binary search.
What is the time complexity of binary search?
O(log n)
It works only on a sorted collection.
What is the time complexity of linear search?
O(n)
What is the average time complexity of efficient sorts like merge sort?
O(n log n)
What does binary search require of its input?
The input must be sorted
What is recursion?
A technique where a function calls itself to solve smaller instances of the same problem
What is the “base case” in a recursive function?
The condition that stops the recursion from continuing
For large inputs, which is faster: an O(n log n) or an O(n²) algorithm?
O(n log n)
What is the time complexity of searching an unsorted array?
O(n)
With no order to exploit, you may have to check every element.
What does “time complexity” measure?
How the number of operations an algorithm performs grows with the input size — not the wall-clock time on a particular machine
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.