Comment by bonoboTP | Hacker News Reader

Comment by bonoboTP | Hacker News Reader

Parent Full thread

Basically, for each input length, you can have different runtimes depending on the contents of that input. If you always pick the highest runtime for each length, that gives you a specific function. You can then derive either a lower or an upper bound for that function. Same for the best case.

You can state four combinations in their common sense intuition as

- even in the worst case, the runtime grows only at most as fast as n^2 (modulo multiplication and addition)

- in the worst case, the runtime can grow at least as fast as n^2

- in the best case, the runtime can grow only at most as fast as n^2

- even in the best case, the runtime grows at least as fast as n^2

One can imagine it as not just a single curve on a function plot, but a band, a range. Then the top line of this range can be bounded from above or below, and the bottom can also be bounded from above or below. The common case is when you give a bound for the top curve, from above.

How to work this into the article, I don't know, sorry.

I appreciate you taking the time to explain this to me, thank you.

I feel like the way I have it is a reasonable, if strictly incorrect, simplification for someone new to the material.

When I write these, I have the newly-hired bootcamp grad as my target audience. Someone who has been taught the basics for how to write code for the web and work as a junior within a company, but has no computer science background. I want them to understand enough to make sense of what they see.

Maybe like this:

"It's common for an algorithm's performance to depend not just on the size of the input, but also its arrangement. In such cases we typically use big O notation to describe the worst-case scenario. However, note that we may perform similar analysis on the best case or the average case as well."

But here:

> You may sometimes see the Greek letter "theta", Θ, instead of the letter O in big O notation. This is used when the best and worst case have the same order of growth. We can't use it for bubble sort because the best case is O(n) and the worst case is O(n^2).

This is plain false, the worst-case runtime of bubble sort is indeed Θ(n^2). Either delete it, or write about the upper bound / lower bound thing.

I made some wording changes based on what you wrote, I'd appreciate your feedback.

I'm struggling to understand how the part about big theta is false. Is the best case for bubble sort not O(n)? I've deleted the section for the time being.

The difference between big theta and big O has nothing to do with worst vs. average case. They are two completely orthogonal axes.

You can talk about the big-O of the average case, the big-theta of the average case, the big-O of the worst case, or the big-theta of the worst case.

Reply on news.ycombinator.com