Big Omega of a while loop

Question

I am learning about running times now and I am having trouble wrapping my head around Big Omega time. So, its safe to say that Big Omega of binary search is Ω(1), because it takes at least constant time.

What if let's say I have a while loop i < n, then its O(n), but does that mean that its Ω(1) or Ω(sqrt(n)) or something else because we can say that it takes at least constant time? I just don't understand, its straightforward with upper bound, but lower bound confuses me a lot.

I am confused about this code. Can we say that its lower bound time is Ω(sqrt(n)) or perhaps Ω(log n), because it can do at least as good?

i=1
while(i<n)
 i+i
end 

Answer 1

Any code that gets executed takes time $\Omega(1)$. That's the most you can say if you don't know anything more about the code. For example, if all your know is that your loop has the form while i < n ..., then it could be that $i = n$, so the loop immediately terminates.

Here are some concrete cases in which we can calculate the complexity:

i = 1
while i < n:
  i = i + 1

This runs in time $\Theta(n)$.

i = 1
while i < n:
  i = i + i

This runs in time $\Theta(\log n)$.

i = 1
j = 1
while i < n:
  i = i + j
  j = j + 1

This runs in time $\Theta(\sqrt{n})$.

See if you can prove all these claims.