For each of the following two functions f(n), determine a simple function g(n)

such that f(n) = Θ(g(n))

• f(n)=(n5 −13n4 +n2logn)(logn+25).

• f(n)=(2n +n2)(n3 +3n).

More problems after this is solved.

Printable View

- Nov 17th 2010, 03:48 PMrandombuddyDiscrete Math Problem
For each of the following two functions f(n), determine a simple function g(n)

such that f(n) = Θ(g(n))

• f(n)=(n5 −13n4 +n2logn)(logn+25).

• f(n)=(2n +n2)(n3 +3n).

More problems after this is solved. - Nov 17th 2010, 11:29 PMemakarov
One man's simple function is another man's nightmare :)

If you have a sum $\displaystyle h_1(n)+h_2(n)$ where $\displaystyle h_1(n)$ dominates, i.e., $\displaystyle h_2(n)=O(h_1(n))$, then $\displaystyle h_1(n)+h_2(n)=\Theta(h_1(n))$. For example, $\displaystyle a_kn^k+a_{n-1}n^{k-1}+\dots+a_1n+a_0=\Theta(n^k)$.

It is customary to write n^2 for $\displaystyle n^2$. It is even better to surround math with [tex] tags, e.g., [tex]f(n)=(2n +n^2)(n^3 +3n)[/tex] for $\displaystyle f(n)=(2n +n^2)(n^3 +3n)$.

Also, you are supposed to show some effort in solving a problem. At least write what you know and what your difficulty is.