Flashcard library · Algorithms
Computer Science: Big-O Notation
Master the fundamentals of Big-O Notation with this essential flashcard deck. Designed for computer science students, these cards cover definitions, common complexities, and practical rules for analyzing algorithm efficiency. Understand why Big-O is crucial for writing performant code and excel in your studies.
Want to actually learn these?
Save this deck to your NoteFren library and study it with spaced repetition — or turn your own notes into cards like these.
What does Big O notation describe?
An upper bound on how an algorithm's time or space grows with input size.
What does n usually stand for in Big O?
The size of the input.
What does O(1) mean? Give an example.
Constant time regardless of input size — like accessing an array element by index.
What does O(log n) mean? Give an example.
Time grows logarithmically, usually by halving the problem — like binary search.
What does O(n) mean? Give an example.
Time grows in proportion to input size — like scanning a list once.
What does O(n log n) mean? Give an example.
Linearithmic time — like merge sort, or quicksort on average.
What does O(n²) mean? Give an example.
Time grows with the square of input size — like selection sort or checking all pairs.
What does O(2ⁿ) mean? Give an example.
Exponential time — like computing Fibonacci numbers with naive recursion.
How are constant factors handled in Big O?
They are dropped: O(2n) simplifies to O(n).
How are lower-order terms handled in Big O?
They are dropped: O(n² + n) simplifies to O(n²).
What is the complexity of a single loop that runs n times?
O(n).
What is the complexity of two nested loops that each run n times?
O(n²).
What is the time complexity of binary search?
O(log n).
What is quicksort's worst-case time complexity?
O(n²), for example with consistently bad pivots on sorted input.
What is the average time to look up a key in a hash table?
O(1), degrading to O(n) in the worst case.