Hacker News new | past | comments | ask | show | jobs | submit login

> Nothing about big-O is specific to worst case

Perhaps technically true but if someone asks you for the time complexity of an algorithm in an interview are you going to say “O(n)” without mentioning you’re referring to average-case? As far as I’m aware, without additional specifiers or context, people are referring to worst-case by default.




I'd say it's the opposite. I've never heard quicksort referred to as a O(n^2) algorithm for example, always as an O(n log n) algorithm with O(n^2) worst-case. Maybe in an interview you would explicitly say average-case, but I think that's more to show the interviewers that you realize that a single algorithm can have multiple big-Os.




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: