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?
cond = false
always, then the initial operation can bei = 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//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 sayi = n;
$\endgroup$ – Jared Jun 4 '14 at 21:08