Algorithm Running Times

The flashcards below were created by user tulipyoursweety on FreezingBlue Flashcards.

  1. Insertion sort: Worst-case
    θ(n2)
  2. Insertion sort: Average-case (expected)
    θ(n2)
  3. Merge sort: Worst-case
    θ(n  lg n)
  4. Merge sort: Average-case (expected)
    θ(n  lg n)
  5. Heapsort: Worst-case
    O(n  lg n)
  6. Quicksort: Worst-case
    θ(n2)
  7. Quicksort: Average-case (expected)
    θ(n  lg n)
  8. Counting sort: Worst-case
    θ(k + n)
  9. Counting sort: Average-case (expected)
    θ(k + n)
  10. Radix sort: Worst-case
    θ(d(k + n)
  11. Radix sort:  Average-case (expected)
    θ(d(k + n)
  12. Bucket sort: Worst-case
    θ(n2)
  13. Bucket sort:  Average-case (expected)
    θ(n)
Author
ID
308777
Card Set
Algorithm Running Times
Description
Algorithm run times - worst and average-case
Updated
Show Answers