Potasse

Cost & complexity

Every card that turns on a cost argument — time, space, or both. Short, and unforgiving about hand-waving.

Add to library

Try a card

Algorithms & data structures1 of 3

What are quicksort's average and worst-case time complexities?

Say it in your head first.

Questions

  1. 01What are quicksort's average and worst-case time complexities?
  2. 02What invariant makes binary search correct?
  3. 03When does a hash table degrade to O(n) lookup?
  4. 04What does amortized O(1) mean for pushing onto a dynamic array?
  5. 05What does a Bloom filter trade away for its small size?
  6. 06What is the cost of building a heap from n elements at once?
  7. 07Why is a balanced BST O(log n) when a plain BST is not?
  8. 08What does memoizing a naive recursive Fibonacci change about its complexity?

…and 2 more cards. The answers are yours to find.