Potasse

Algorithms & data structures

The classics, asked as questions rather than definitions. Why a structure behaves as it does, not just its big-O.

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. 02Why is merge sort preferred over quicksort for linked lists?
  3. 03What invariant makes binary search correct?
  4. 04When does a hash table degrade to O(n) lookup?
  5. 05What does amortized O(1) mean for pushing onto a dynamic array?
  6. 06Why does BFS find a shortest path on an unweighted graph when DFS does not?
  7. 07Why does Dijkstra's algorithm break on negative edge weights?
  8. 08What does a Bloom filter trade away for its small size?

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