2
$\begingroup$

Sorry if this question is very simplistic; I'm just starting out and I'm trying to wrap my head around all this asymptotic bound stuff. When trying to find the upper bound for the worst case of a function does it need to take into account what the meat of the code actually does? I have some code that would (in the worst case) iterate through a while loop n times, but when you consider what that code actually does, it would always make it so that the condition for the while loop becomes false on the next iteration.

Some people say that it doesn't matter what is actually happening within the code; just that if it has the ability to iterate n times (even though it's virtually impossible because of the body of the loop) then that would be the worst case vs. however many steps the code ACTUALLY runs.

If anyone has any insight it would be greatly appreciated! Thanks!

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ If there's no possible input which makes the loop run $n$ times then that does NOT contribute a factor of n to the complexity of the function. However, if you're talking about big O then, since big O is an upper bound, it wouldn't be incorrect to include that factor of $n$ in the complexity, but the bound obtained wouldn't be the lowest possible upper bound (which is usually the upper bound of interest). This is a very informal comment, maybe someone with more time can give a more precise answer. $\endgroup$
    – Sam Jones
    Commented Dec 5, 2012 at 21:52
  • 3
    $\begingroup$ In fact, I think there needs to be a potentially infinite number of inputs for which your code takes a number of steps proportional to $f(n)$, before you cannot claim to be better than $O(f(n))$. If the number of inputs for which your code does poorly is finite, you may ignore them as far as asymptotic complexity is concerned. $\endgroup$
    – Patrick87
    Commented Dec 5, 2012 at 21:58

1 Answer 1

Reset to default
2
$\begingroup$

It matters what is actually happening in the code. The following pseudocode is O(1)

loop_factor = input()

for x between 0 and loop_factor():
    for y between 0 and loop_factor():
        terminate

However, it doesn't matter what is likely or reasonable to happen. If the body of your loop makes it "virtually" guaranteed that the loop will terminate next iteration, that means nothing; you need an actual hard proof that the loop will exit early for all input, no matter how absurd.

Essentially if you can rewrite your algorithm so that the loop clearly can't iterate n times without changing the meaning (i.e. replace the loop with just a few copies of the loop body in if statements, or something), then you are justified in saying that the loop isn't going to do n iterations. If you really need the loop to be there in the code as a loop that can iterate up to n times, then the big-oh complexity of the loop almost certainly does have to be n times the complexity of the loop body.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for your answer, that was extremely helpful. The actual while loop looks like it can be replaced by if statements because of what the loop actually does, but I'm assuming that because it was written as a while it should be calculated as something that could potentially iterate up to n times. Am I correct in thinking this? $\endgroup$
    – Peelings
    Commented Dec 5, 2012 at 22:45
  • $\begingroup$ @Peelings Kind-of, but not really. Looking at loops and multiplying is just a quick heuristic for estimating big-oh complexity that works very well in practice for working programmers. Programmers are normally not particularly interested in the formal proofs necessary to show that a program with two nested loops is actually O(n^1.5) rather than O(n^2); they'd rather glance at the program and conclude that two loops = n^2, and then work with profilers to optimize the actual runtime. $\endgroup$
    – Ben
    Commented Dec 5, 2012 at 23:03
  • $\begingroup$ @Peelings But if there was a formal proof that the program won't use "all" of its potential "loopiness" and so can be described by O(n^1.5), then a theoretician would be uninterested in the argument that goes "it's got two nested loops, each of which can iterate up to n times, so it's O(n^2)". $\endgroup$
    – Ben
    Commented Dec 5, 2012 at 23:05
  • $\begingroup$ This is the part that gets me; essentially the loop in question goes through a list of numbers and if the element is even it will add 1 to it. Once the number becomes odd, it will fail the loop condition. So even though it seems impossible for this loop to continue n times, it could potentially do it if all the numbers were magically always even, even after adding a 1 to it. Is this the kind of absurd input you were talking about? $\endgroup$
    – Peelings
    Commented Dec 5, 2012 at 23:36
  • $\begingroup$ @Peelings If it's really adding 1 to the same integer repeatedly until it becomes odd (where is the list of numbers involved? Are you sure it's not adding 1 to each element of the list until it finds an odd element of the list?), then that's a straightforward proof that it can never execute the loop body more than 2 times. That's a hard guarantee, given the usual properties of integers. You don't have to worry about impossible inputs, only the worst possible ones. :) $\endgroup$
    – Ben
    Commented Dec 6, 2012 at 0:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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