Math Is Fun Forum

greggo72

Member

Registered: 2014-03-05

Posts: 1

Prove or disprove

Can someone please explain this? I'm not understanding this topic at all. Thanks!

Prove or disprove :
a) f(n) = 2^(n+1) = O(2^n)
b) f(n) = 2^(n+1) = theta(2^n)
c) f(n) = 2^2n = O(2^n)
d) f(n) = 2^2n = theta(2^n)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Prove or disprove

Hi;

a)

2^(n+1) = 2 * 2^n so we can say 2^(n+1) =O(2^n), this comes from the definition of O.

c) I would say that is false.

Check this pdf out:

http://www.cs.utsa.edu/~bylander/cs3233/big-oh.pdf

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.