Learn Big O Notation with 44 Flashcards: Complexity Classes, Θ and Ω, and Sorting Costs
Learn Big O notation with 44 real flashcards: O(1) to O(2ⁿ), Big Theta and Omega, quicksort and merge sort costs, Dijkstra, plus three cards worth rewriting.
Studying. But it's also a video game. 🎮
Flashcards, quizzes and games that make you actually remember.
Posted by
FLIP IT TeamRelated reading
Master Dynamic Programming with 30 Flashcards: Memoization, Knapsack, LCS and Bitmask DP
Master dynamic programming with deck AI3432: 30 flashcards on memoization, tabulation, knapsack, LCS, LIS, edit distance, Kadane, bitmask and digit DP.
Study Guide: Software Testing in 40 Flashcards — Unit, Integration and 30 More Test Types
Learn software testing with 40 flashcards: unit vs integration, the test pyramid, smoke vs sanity, load vs stress, code coverage, mutation testing and TDD.
Learn Big O Notation in German: 44 Flashcards on Landau-Notation, Schranken and Sorting Costs
German edition of the Big O flashcard deck: obere, untere and scharfe Schranke, Mergesort, Knoten and Kanten, plus three cards to fix before you study.
Big O questions show up in every coding interview, yet most people only half-know them: they remember that binary search is "log n" but freeze when asked what Θ means or why the log base doesn't matter. Deck OF1426 – Big O Notation on Flip It packs both halves into 44 flashcards: the notation itself and the complexities you are expected to quote on demand.
Study this deck: Big O Notation
1 / 10Big O notation
Tap the card for the answer · swipe right if you knew it, left if not
What the cards actually ask
| Front | Back |
|---|---|
| O(log n) complexity | Logarithmic time, typical for algorithms that halve the problem each step (binary search) |
| O(n log n) complexity | Linearithmic time, typical for efficient comparison sorts like merge sort and heapsort |
| Worst-case time complexity of quicksort | O(n²) |
| Time complexity of insertion sort | O(n²) worst and average, O(n) best case |
| Big Theta (Θ) notation | f is bounded by g above and below (tight bound) |
| Can you drop lower-order terms? | Yes: O(n² + n) = O(n²) |
| Is log₂(n) different from log₁₀(n) in Big O? | No, O(log₂ n) = O(log₁₀ n) = O(log n) |
| Time complexity of Dijkstra with a binary heap | O((V + E) log V) |
| Inverse Ackermann function's complexity | O(α(n)), effectively constant (disjoint-set operations) |
Everything the deck covers
O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n³) naive matrix multiplication; little-o, Big Omega (Ω), Big Theta (Θ), asymptotic equivalence (~), Soft-O (Õ), Vinogradov's ≪; polylogarithmic, superpolynomial and subexponential functions; space complexity, in-place algorithms, amortized time; best, average and worst case; binary search, linear search, quicksort, merge sort, bubble sort, insertion sort; Dijkstra, Bellman-Ford O(VE), Floyd-Warshall O(V³); Knuth's role in the 1970s and the German Ordnung behind the letter O.
How to study it
Split the deck in two. The cards alternate between notation theory (cards 1-12, 25-33, 37-38, 42) and a complexity lookup table (13-24, 34-36, 39-41). Learn the lookup table first: it is what interviews test, and the abstract cards (superpolynomial, Soft-O, Vinogradov) make far more sense once you can rank real algorithms. Then take the theory block as a second pass.
Quiz yourself on the why, not just the label. For every complexity card, say the reason aloud before flipping: quicksort is O(n²) because a bad pivot leaves one empty side at every level; insertion sort drops to O(n) on sorted input because each element is compared once. A reason survives the interview; a memorized label does not.
Three cards worth rewriting
- Card 15 asks for the best possible comparison sort and answers "O(n log n) in the average case". The real fact is a lower bound: any comparison sort needs Ω(n log n) comparisons in the worst case (and on average). Rewrite it with Ω.
- Card 3 is shown as
F(n) = O(g(n)): restore the lowercase f, and pair it with card 30 so you remember the = really means f ∈ O(g). - The deck uses O(n²) and O(n³) in its answers but never gives them a class card. Add two: O(n²) = quadratic (nested loops over the input) and O(n!) = factorial (brute-force permutations, e.g. naive travelling salesman).
Go further
Once the cheat sheet is solid, attach each complexity to a real implementation with our sorting, searching and graph algorithms guide and the hash tables, heaps and tries of our data structures article.
Search for OF1426 in the Flip It library to start drilling.
Ready to learn faster? 🚀
Join FLIP IT for free and turn studying into a game.