1
$\begingroup$

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 
$\endgroup$
  • $\begingroup$ In this particular case the code is $\Theta(n)$ (assuming you meant i = i+1). $\endgroup$ – Yuval Filmus Mar 3 '16 at 21:07
  • 2
    $\begingroup$ You are changing the question, though, and this makes it harder to answer – each revision will need its own answer. Perhaps you need to do this interactively with a teaching assistant in person, rather than online; the stackexchange format is suitable for such prolonged discussions. $\endgroup$ – Yuval Filmus Mar 3 '16 at 21:08
  • $\begingroup$ Sorry, I meant i gets doubled. Like i was 1 on first iteration, then its 2, then 4, then 8 and so on on each iteration. I should have written it another way. $\endgroup$ – Romaldowoho Mar 3 '16 at 21:10
  • $\begingroup$ Then it's $\Theta(\log n)$. You see – the running time depends on the actual code. $\endgroup$ – Yuval Filmus Mar 3 '16 at 21:10
  • 1
    $\begingroup$ Moderator notice: Please do not delete answered questions, even if you're able to. This is a question and answer site, not a homework support site. Answers on this site are not just for you, they're for everyone. $\endgroup$ – Gilles 'SO- stop being evil' Mar 4 '16 at 13:46
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So let's say I am increasing my i in the while i < n loop. Can I say that the lower bound will be Ω(sqrt(n))? Since I update my i inside a while loop and it can do as good as Ω(sqrt(n))? $\endgroup$ – Romaldowoho Mar 3 '16 at 20:42
  • $\begingroup$ No, you can't say anything better in general since, for example, $i$ might be larger than $n$ to begin with; or some instruction might say $i$ to equal $n$ during the first iteration. You can't get a meaningful time lower bound without looking at the code, any more than you can do the same for time upper bounds. $\endgroup$ – Yuval Filmus Mar 3 '16 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.