0

I need to prove this

(n+2)/2^n=Θ(1)

i found an explanation saying that because the growth ratio of the denominator is larger than the growth ratio of numerator but i don't believe that's the case for every division 1/n isn't Θ(1) for example. if it is possible i must find this without the use of the limit definition

kaya3
  • 47,440
  • 4
  • 68
  • 97
Petros Venieris
  • 1
  • 2
  • Is that (n + 2) / 2^n, or n + 2/2^n? – templatetypedef Apr 23 '21 at 16:31
  • (n+2)/2^n i will change it – Petros Venieris Apr 23 '21 at 16:46
  • 2
    It's not Theta(1). (n+2)/2^n is not bounded below by any non-zero multiple of 1, which is one of the conditions for it being Theta(1). (The other condition being bounded above, which it does satisfy). – Paul Hankin Apr 23 '21 at 17:29
  • @PaulHankin I think Ω(1) does bound it from below. May you add an answer to be more specific where my reasoning might be wrong? – AKSingh Apr 23 '21 at 18:12
  • @PaulHankin You're right, of course. I did not realise that when talking about functions that tend toward 0, Θ is no longer insensitive to constant terms. I deleted my answer to avoid spreading lies :) – Berthur Apr 23 '21 at 18:15
  • @AKSingh There is some discussion here: https://stackoverflow.com/questions/18677537/what-is-the-difference-between-o1-and-%CE%981 – Berthur Apr 23 '21 at 18:23

1 Answers1

1

You may try to answer this by using recursive proof.

Proving that it is O(1)

Initialization

For n0=2, (n0+2)/2^n0 = 1 <= 1

Generalization

Let n a non nul natural number such that (n+2)/2^n <= 1.

Then, n+2 <= 2^n

Since n >=1 , 2^n >1, so 2^n + 2^n > 2^n + 1

So, n+2 + 1 <= 2^n +1 <= 2 * 2^n, meaning that (n+1)+2 <= 2^(n+1), so ((n+1)+2)/2^(n+1) <= 1

Conclusion

For all n >= n0 = 2, (n+2)/2^n <= 1, meaning that (n+2)/2^n = O(1)

Edit

As @Paul Hankin mentioned, it isn’t Theta(1) since its limit is 0.

TUI lover
  • 542
  • 4
  • 16