Flashcards · Big-O Notation · Free
Big-O Notation flashcards, generated for you.
Example Big-O Notation study cards to learn from right now — then generate a full set from your own notes (plus a practice quiz) and export to Quizlet or Anki. Free, no account needed.
Example Big-O Notation flashcards
What does Big-O notation measure?
The worst-case upper bound on how an algorithm's runtime or space grows as input size n increases, independent of constant factors and lower-order terms.
What is the difference between O(1) and O(n)?
O(1) means constant time regardless of input size (e.g., accessing array index). O(n) means time grows linearly with input size (e.g., simple loop). O(1) is vastly superior at scale.
Why do we ignore constants in Big-O? Give an example.
Constants don't change the growth rate or relative performance at scale. An O(5n) algorithm and O(n) algorithm both become dominated by n when n is large, so both are written O(n).
Rank these from fastest to slowest: O(n²), O(n), O(log n), O(1), O(2^n)
O(1) < O(log n) < O(n) < O(n²) < O(2^n). Exponential is catastrophically slow; constant is best.
What does O(log n) typically indicate about an algorithm's strategy?
The algorithm eliminates roughly half the remaining problem space with each step (divide-and-conquer or binary search). Common in balanced trees and sorted array searches.
When analyzing a nested loop, how do you determine Big-O?
Multiply the complexities of each loop. Two nested loops each iterating n times = O(n) × O(n) = O(n²). If inner loop runs k times: O(n × k).
What is the Big-O trade-off between time and space?
Often you can reduce time complexity by using extra space (caching, hash tables, precomputation). Example: trading O(n²) time for O(n) space via a hash map for lookups.
Why is O(n log n) important in sorting?
O(n log n) is the theoretical lower bound for comparison-based sorting (merge sort, quicksort, heapsort achieve it). Faster than O(n²) but slower than linear sorts with constraints.
How does Big-O differ from actual runtime? Name two reasons.
1) Constants and lower terms hidden in Big-O: O(100n) looks like O(n) but is 100× slower. 2) Big-O ignores real-world factors like cache locality, memory access patterns, and constant operations.
When would you choose an O(n²) algorithm over an O(n log n) algorithm in practice?
When n is small (hidden constants favor simpler code), when the O(n log n) algorithm has huge constant factors, or when O(n²) has better cache locality or easier implementation with lower real-world overhead.
Make your own Big-O Notation study set
Flashcards for related topics
Studying Big-O Notation to build with AI? MindloomHQ turns it into real skills — structured courses, agent projects, and certificates.
Explore MindloomHQ →