2
$\begingroup$

I have an algorithm similar to this:

i=1
while(i < n) {
  //something in O(1)
  while(i < n && cond) {
    //something in O(1)
    i++
  }
  i++
}

Where "cond" is some condition which can be checked in $\mathcal O(1)$. It is clear that this algorithm is $\mathcal O(n^2)$. But is it also $\mathcal O(n)$?

I'd say yes because the statement "i++" is executed $\mathcal O(n)$-times since both loops end when i reaches n.

Is it possible to rewrite the algorithm in a form with equivalent runtime so that it can be seen more clearly?

|cite|improve this question
$\endgroup$
  • $\begingroup$ There are assumptions to this problem that you are not making. Let's assume that cond = false always, then the initial operation can be i = i - 1. This will cause this program to never end (to not halt) and thus there is no big-Oh you can give to this program. $\endgroup$ – Jared Jun 2 '14 at 9:11
  • $\begingroup$ The statements in between do not modify i. i is only modified in "i=1" and "i++". $\endgroup$ – ljfa Jun 2 '14 at 9:17
  • 1
    $\begingroup$ Our reference questions on algorithm analysis and Landau notation may shed some light. $\endgroup$ – Raphael♦ Jun 2 '14 at 12:21
  • $\begingroup$ @ljfa "The statements in between do not modify i. i is only modified in "i=1" and "i++"." This is an assumption you did not make clear, you have: //something in O(1). i = i - 1; is in $\mathcal{O}(1)$. It could also be in $\mathcal{\Theta}(1)$ if that $\mathcal{O}(1)$ operation was say i = n; $\endgroup$ – Jared Jun 4 '14 at 21:08
5
$\begingroup$

What you have there is not a true nested loop. It's one loop with, what is equivalently an if-test in there, like:

while(i<n){
   if(cond)
      //something Θ(1)
   else
      //some other Θ(1) thing
   i++
}

Notice in your case, you have the same variable for both loops with no reset.

So, to answer your question, the running time is $\Theta(n)$. In particular, it is $O(n)$.

As a commenter states, anything that is $O(n)$ is also $O(n^2)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Your pseudocode implies a $\mathcal{O}(n^2)$ runtime. Your reasoning is correct though. $\endgroup$ – Jared Jun 2 '14 at 8:38
  • 1
    $\begingroup$ $O(n^2)$ denotes an upper bound. So anything that is $O(n)$ is also $O(n^2)$. In your first sentence you seem to confuse $O()$ with $\Theta()$. $\endgroup$ – FrankW Jun 2 '14 at 8:38
  • $\begingroup$ @d'alar'cop Your reasoning is flawed then--it cannot be simply put into an $\mathcal{O}(1)$ for each loop--you need something more sophisticated. $\endgroup$ – Jared Jun 2 '14 at 8:43
  • $\begingroup$ I think your loop is correct--I just think you need to do a little more to justify it...I'm giving an answer as such. $\endgroup$ – Jared Jun 2 '14 at 8:45
  • 2
    $\begingroup$ "NB: I'm guessing that what you intended was $\Theta$, not $O$." That seems very unlikely. Anything that is $\Theta(n^2)$ is definitely not $\Theta(n)$ so it would be odd to ask about that. But something that is $O(n^2)$ may very well be $O(n)$ so that is a reasonable question. (Quicksort is $O(2^n)$!) $\endgroup$ – David Richerby Jun 2 '14 at 11:19

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.