0
$\begingroup$

How can I find the cost of pseudocode with a nested loop and a nested if statement?

Exercise

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.

$\endgroup$
  • 2
    $\begingroup$ Don't use images as main content of your post. Not only is it lazy, it also makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and maths (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael Feb 20 '14 at 11:10
  • 1
    $\begingroup$ What kind of costs are you after -- best, average or worst case; lower or upper bound or exact result? What is your guess? $\endgroup$ – Raphael Feb 20 '14 at 11:11
  • $\begingroup$ Mentioning the book that you follow is not considered an ad. Just say "Algorithms" by Cormen, etc. $\endgroup$ – sakisk Feb 20 '14 at 13:23
2
$\begingroup$

Big O analysis

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)

Cost analysis

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

$\endgroup$
  • $\begingroup$ "eliminate all constant time operations" -- then every algorithm runs in zero time. "You always assume worst case." -- usually and if not stated otherwise, but not always. $\endgroup$ – Raphael Feb 20 '14 at 11:13
  • $\begingroup$ @Raphael "eliminate all constant time operations" means that constant time operations do not ADD to the complexity. Start assuming algorithm "will always be at least O(1)", and then look for features that increase it beyond that. $\endgroup$ – SeeMoreGain Feb 20 '14 at 11:29
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.