CODEWITHSUNDEEP
algorithmbig-ocomplexity-theory
scy17
scy17

Reputation: 61

How to prove/disprove if (2^{n})^{1/3} is in Θ(2^{n}) using Big-O, Big-Omega and Big-Theta

So I understand Big-O, Big-Omega and Big-Theta conceptually, but I'm not sure how to prove Big-Omega and Big-Theta.

function f is in Big-O(g) if and only if there exists some constant c > 0 and some constant n_0 ≥ 1 such that for all n ≥ n_0, the expression f(n) ≤ c·g(n) is true.

Big-Omega is the opposite, c·g(n) ≤ f(n).

Big-Theta sandwiches c1·f(n) ≤ g(n) ≤ c2·f(n).

I need to prove/disprove if (2^{n})^{1/3} ∈ Θ(2^{n}) by using all three notations.

What I have so far:

Big-O : (2^{n})^{1/3} ≤ c·2^{n} when c=1 and n_0 = 1, so (2^{n})^{1/3} ∈ O(2^{n})

Big-Omega : We can rewrite (2^{n})^{1/3} = (1/(2^{2n/3}))·(2^n). We see that for c·g(n) ≤ f(n), c has to be ≤ 1/(2^{2n/3}) which is not possible since c > 0. So, there does not exist a c > 0 that satisfies c·g(n) ≤ f(n) and thus, (2^{n})^{1/3} ∉ Ω(2^{n})

Big-Theta : Since (2^{n})^{1/3} ∉ Ω(2^{n}), there is no lower bound c1·f(n) ≤ g(n). Therefore, (2^{n})^{1/3} ∉ Θ(2^{n})

Is this how you are supposed to prove it?

Upvotes: 0

Views: 843

Answers (1)

OmG
OmG

Reputation: 18858

First simplify f(n) = (2^n)^(1/3) to f(n) = 2^(n/3). Then, take a limit of lim_{n\to\infty} f(n)/g(n) that g(n) = 2^n:

lim_{n\to\infty} 2^(n/3) / 2^n = lim_{n\to\infty} 1 / 2^(2n/3) = 0

Hence, f(n) = o(g(n)) (little-oh). It means f(n) is not in \Theta(g(n)). Notice that f(n) = O(g(n)) (Big-Oh) as it is in o(g(n)) (little-Oh).

Upvotes: 0

Related Questions