I'm studying algorithm complexity and big O notation. I have these two functions that express time complexity: $f(n) = 2^n$ and $g(n) = 2n^3$.
The question is, when is g(n) dominated by f(n)? To solve it, I know I need to find a value for n where $f(n) > g(n)$. I tried multiple ways, using log properties, but I didn't get anywhere.
This is how far I got:
$$2^n > 2n^3$$
$$2^{n-1} > n^3$$
$$\log_n2^{n-1} > 3$$
$$(n-1)\log_n2 > 3$$
$$\log_n2 > 3\cdot\frac{1}{(n-1)}$$
$$2 > n^{\frac{3}{(n-1)}}$$
If I go any far, I end up going in circles. I'll appreciate any explanations or hints on this problem.
I'll appreciate any explanations or hints on this problem.
Best Answer
If $n$ is an integer, we can use a guess-and-check approach. Since we know $2^{10} = 1024$ and $10^3 = 1000$, clearly $n > 10$. Then calculating each side for $n \in \{11, 12, \ldots\}$ we see that the first instance where the inequality is satisfied is when $n = 12$.
Alternatively, Newton's method applied to $\log \frac{f(n)}{g(n)}$ will work: we have $$n_{k+1} = \frac{n_k (3 \log n_k + \log 2 - 3)}{n_k \log 2 - 3},$$ and with a suitable initial guess, say $n_0 = 10$, we get the sequence of iterates $$n_1 \approx 11.7027, \\ n_2 \approx 11.6132, \\ n_3 \approx 11.6130, \\ n_4 \approx 11.6130.$$