# Properly Solving a Big O Proof

• Jan 21st 2011, 01:09 PM
RageD
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) <br /> img.top {vertical-align:15%;}<br /> $5^{\log_{5}(n)}$ and <br /> img.top {vertical-align:15%;}<br /> $3n+2$ (2) <br /> img.top {vertical-align:15%;}<br /> $n^2$ and <br /> img.top {vertical-align:15%;}<br /> $(\sqrt{3})^{\log(n)}}$
So for the first one I get to a point similar to this:

Code:

 <br /> img.top {vertical-align:15%;}<br /> $5^{\log_{5}(n)} = n$ so new question: <br /> img.top {vertical-align:15%;}<br /> $n$ is <br /> img.top {vertical-align:15%;}<br /> $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 $c$ and $k$ (k is the same as $n_0$) must make this statement true (where f(x) = original and g(x) = bound equation):

Code:

 <br /> img.top {vertical-align:15%;}<br /> $f(x) \le c*g(x)$ for every number <br /> img.top {vertical-align:15%;}<br /> $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.

• Jan 21st 2011, 03:54 PM
Sudharaka
Quote:

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) <br /> img.top {vertical-align:15%;}<br /> $5^{\log_{5}(n)}$ and <br /> img.top {vertical-align:15%;}<br /> $3n+2$ (2) <br /> img.top {vertical-align:15%;}<br /> $n^2$ and <br /> img.top {vertical-align:15%;}<br /> $(\sqrt{3})^{\log(n)}}$
So for the first one I get to a point similar to this:

Code:

 <br /> img.top {vertical-align:15%;}<br /> $5^{\log_{5}(n)} = n$ so new question: <br /> img.top {vertical-align:15%;}<br /> $n$ is <br /> img.top {vertical-align:15%;}<br /> $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 $c$ and $k$ (k is the same as $n_0$) must make this statement true (where f(x) = original and g(x) = bound equation):

Code:

 <br /> img.top {vertical-align:15%;}<br /> $f(x) \le c*g(x)$ for every number <br /> img.top {vertical-align:15%;}<br /> $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,

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

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

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

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

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

Hope you understood.
• Jan 22nd 2011, 08:29 AM
emakarov
Quote:

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 $c_nx^n+\dots+c_1x+c_0\le x^n(c_n+\dots+c_1+c_0)$ for $x\ge 1$.

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