# Thread: Properly Solving a Big O Proof

1. ## Properly Solving a Big O Proof

Hello,

I am currently taking a class which is covering a topic which I have not yet had experience with. I have done a lot of research on the topic, and believe to understand the definition well, however, I'm not sure how to go about truly applying the definition.

I will type up the question below with modified numbers so I can see how to really solve the problem rather than simply receiving the answer.

The questions are as follow:

Code:
Indicate for each of the following pairs of expressions (A,B) whether A is O, Ω, Θ of B.

(1) $\displaystyle 5^{\log_{5}(n)}$ and $\displaystyle 3n+2$
(2) $\displaystyle n^2$ and $\displaystyle (\sqrt{3})^{\log(n)}}$
So for the first one I get to a point similar to this:

Code:
$\displaystyle 5^{\log_{5}(n)} = n$
so new question:
$\displaystyle n$ is $\displaystyle O(3n+2)$
But I'm not sure how to draw the proof from here. I understand that Big O is the upper-bound of a function and to prove it, some numbers $\displaystyle c$ and $\displaystyle k$ (k is the same as $\displaystyle n_0$) must make this statement true (where f(x) = original and g(x) = bound equation):

Code:
$\displaystyle f(x) \le c*g(x)$ for every number $\displaystyle x \ge k$
My biggest issue is finding my numbers c and k. Are these arbitrary values which make the statement true or is there a better way to find them?

As for the second set of numbers, I'm just not exactly sure where to begin. Again, I have changed the numbers so there are not my homework problems, but do highly resemble them. So I appreciate concept explanations over answers - the answers are irrelevant if I don't understand the concept.

2. Originally Posted by RageD
Hello,

I am currently taking a class which is covering a topic which I have not yet had experience with. I have done a lot of research on the topic, and believe to understand the definition well, however, I'm not sure how to go about truly applying the definition.

I will type up the question below with modified numbers so I can see how to really solve the problem rather than simply receiving the answer.

The questions are as follow:

Code:
Indicate for each of the following pairs of expressions (A,B) whether A is O, Ω, Θ of B.

(1) $\displaystyle 5^{\log_{5}(n)}$ and $\displaystyle 3n+2$
(2) $\displaystyle n^2$ and $\displaystyle (\sqrt{3})^{\log(n)}}$
So for the first one I get to a point similar to this:

Code:
$\displaystyle 5^{\log_{5}(n)} = n$
so new question:
$\displaystyle n$ is $\displaystyle O(3n+2)$
But I'm not sure how to draw the proof from here. I understand that Big O is the upper-bound of a function and to prove it, some numbers $\displaystyle c$ and $\displaystyle k$ (k is the same as $\displaystyle n_0$) must make this statement true (where f(x) = original and g(x) = bound equation):

Code:
$\displaystyle f(x) \le c*g(x)$ for every number $\displaystyle x \ge k$
My biggest issue is finding my numbers c and k. Are these arbitrary values which make the statement true or is there a better way to find them?

As for the second set of numbers, I'm just not exactly sure where to begin. Again, I have changed the numbers so there are not my homework problems, but do highly resemble them. So I appreciate concept explanations over answers - the answers are irrelevant if I don't understand the concept.

Dear RageD,

$\displaystyle 5^{\log_{5}(n)} = n~\forall ~n~\geq{0}$

Therefore, $\displaystyle 5^{\log_{5}(n)}\leq{3n}<3n+2~\forall ~n~\geq{0}$

$\displaystyle 5^{\log_{5}(n)}<3n+2~\forall ~n~ \geq{0}$

As you can see, k=0 and c=1 in this case.

Hence, $\displaystyle n=5^{\log_{5}(n)}\in{O(3n+2)}$

Hope you understood.

3. My biggest issue is finding my numbers c and k. Are these arbitrary values which make the statement true or is there a better way to find them?
The answer is, yes and yes. To have a proof that f(x) is O(g(x)) is it sufficient to find any c and k at all as long as |f(x)| <= c * |g(x)| for x >= k. But there are standard ways to find upper and lower bounds of functions. For example, it is typical to use the fact that $\displaystyle c_nx^n+\dots+c_1x+c_0\le x^n(c_n+\dots+c_1+c_0)$ for $\displaystyle x\ge 1$.

For the second problem, assuming logarithm is to the base 2, $\displaystyle \sqrt{3}^{\log n}=(2^{\log\sqrt{3}})^{\log n}=(2^{\log n})^{\log\sqrt{3}}=n^{(\log 3)/2}$. Since $\displaystyle \log_2 3<\log_24=2$, $\displaystyle n^2/(n^{(\log 3)/2})=n^{2-(\log 3)/2}$ becomes greater than any particular constant c. Therefore, $\displaystyle n^2$ cannot be less than $\displaystyle cn^{(\log 3)/2}$ from some $\displaystyle n$ on.