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
i = i+1
). $\endgroup$ – Yuval Filmus Mar 3 '16 at 21:07