Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
How can I find the cost of pseudocode with a nested loop and a nested if statement?
On the left hand side is an example from a textbook I am following. On the right hand side is pseudo code that I found. I took a guess, but I don't know what the time would be for the inner code fragments.
I am especially unsure what the code segments inside the if statement would be because the if statement doesn't always occur.
The answer is O(n^2).
Good strategy for working this out is eliminate all constant time operations (unless it is a return / break that will change the loop), as everything will always be at least O(1).
This means you can eliminate everything inside the if, as well as the if. So you are left with a simple nested loop running over n
Hence O(n^2)
You always assume worst case (unless explicitly told otherwise). Therefore assume if statement will be true and statements will run every loop (as there can exist a sorting order where this is true), so your statements will have the same cost as your loop
For this particular snippet of code, the answer is that it doesn't matter that the if statement is only entered "sometimes". If the if statement is entered, then you only do a constant amount of additional work. This is asymptotically equivalent to even evaluating if the if statement should be entered or not. Whether you enter or not is immaterial.
If the code inside were more complex, then you could naively construct an upper bound by assuming it always enters the block. It may be the case that this actually produces an "incorrect" (too loose) bound, but for sufficiently complex code one may require an entire paper to prove that a block is only entered a small number of times. Or, worst of all, it may in fact be impossible to prove when it is entered. Therefore as a first pass, it would be good enough to assume it's always entered. In practice, the result you get is often tight, or "tight enough". Otherwise, you better start busting out some serious proofs.
Anyway, for this particular snippet, the runtime of the code becomes the result of the sum you've expressed. Thankfully, this is is an exceedingly common sum which we all take the result of for granted. Here it is plugged into wolfram. The answer is something vaguely complex that there are various proofs of, but the key point is that its dominant factor is $n^2$, which is all we ever care about in asymptotics. Therefore this code runs in $O(n^2)$.
You could have also achieved this bound using similar reasoning I applied to the if statement: be lazy, and assume the worst. In this case, the inner loop does the most iterations when $i=1$. So let's just assume that it's always the case. Then that loop always goes from $1$ to $n$, and the two loops combined do $n*n = O(n^2)$ work. Hey look, that's the same bound. Awesome.
It's easy to get bogged down in minor details with asymptotics, but you should generally try to be as "lazy" as possible to keep your analysis sane. Often (especially as you work with more examples), you will have an intuition for what the answer will be, or at least a target for how good it needs to be. Always start with the naivest, laziest upper bound you can think of (as long as it is indeed "upper"), and if it's "good enough", just stop there.
