# Nested loops: Still $\mathcal O(n)$?

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?

• 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. – Jared Jun 2 '14 at 9:11
• The statements in between do not modify i. i is only modified in "i=1" and "i++". – ljfa Jun 2 '14 at 9:17
• Our reference questions on algorithm analysis and Landau notation may shed some light. – Raphael Jun 2 '14 at 12:21
• @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; – Jared Jun 4 '14 at 21:08

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)$.

• Your pseudocode implies a $\mathcal{O}(n^2)$ runtime. Your reasoning is correct though. – Jared Jun 2 '14 at 8:38
• $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()$. – FrankW Jun 2 '14 at 8:38
• @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. – Jared Jun 2 '14 at 8:43
• 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. – Jared Jun 2 '14 at 8:45
• "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)$!) – David Richerby Jun 2 '14 at 11:19