search

DanielHabib / terminal-based-comp-sci-quiz

Terminal Based Computer Science assessment
28 stars 9 forks source link

Some Problems contain incorrect answers and lack clarity #6

Open DanielHabib opened 8 years ago

DanielHabib commented 8 years ago

Shared by djimbob on reddit: https://www.reddit.com/r/programming/comments/5cm0p1/terminal_based_computer_science_assessment/

E.g., Quicksort's time complexity is O(n2) in the worst case. Also big-O isn't a "largest lower bound" asymptotic behavior; big O means an upper bound (and you commonly quote the smallest though every O(n2) function is also O(n3). You could say it's little-o of o(n log n), but you rarely think about little-o time complexity (and best case little-o is o(n) when all elements of the array are identical).
DanielHabib commented 8 years ago

I fixed the typos changing O=>Ω I followup and confirm that this is the appropriate analysis of quicksorts runtimes