Nested loops: Still $\mathcal O(n)$? I have an algorithm similar to this:

i=1
while(i &lt; n) {
  //something in O(1)
  while(i &lt; n &amp;&amp; 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?
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&lt;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)$.