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.

Thank you for your help!