Big $O$ -- $k^n$ vs $(k-1)^n\cdot n$, $(k>1)$

25 Views Asked by At

I tried to do the following:

$$ k^n = (k-1)^n\cdot \left(\frac{k}{k-1}\right)^{n}$$

Now if i compare the above expression on the R.H.S with $$(k-1)^n \cdot n$$ I just need to compare $n$ and $\left(\frac{k}{k-1}\right)^{n}$.

Now $\frac{k}{k-1}$ will definitely be greater than 1, so let $\frac{k}{k-1} = c$ , so this will reduce into $c^n$ which is greater than n.

Where am i going wrong?

The answer given is that $(k-1)^n\cdot n > k^n$

1

There are 1 best solutions below

0
On BEST ANSWER

Given answer obviously is wrong. Let's take $k=2$. Then your given answer will be $n>2^n$ which is false for $\forall n \in \mathbb{N}$. So you going wrong, when you trust given answer.