How do I solve exercise 1.2-2 from
Introduction to Algorithms 3rd Edition, Author: Thomas H. Cormen
Would I need to set both sides equal to each other and solve for n?
[Math] merge sort vs insertion sort time complexity
algorithmsasymptoticslogarithms
Related Solutions
Assuming (as Jesko does) that $q$ is a constant and not part of the input, the usual long-division algorithm you learn at school will do quite nicely. The algorithm is the following:
Compute multiples $q$, $2q$, $3q$, $4q$, $\dots$, $10q$. This takes constant time, as it's independent of $q$.
Say $q$ has $k$ digits. Start with the first $k$ digits of $p$. Call this string $s$.
Compare it against each of the $10$ multiples of $q$; whichever $cq$ is the largest one smaller than $s$, write down $c$ as a digit of answer, subtract $cq$ from $s$, and "bring down" the next digit of $p$. That is, set $s$ to be $(s - cq)$ concatenated with the next digit of $p$.
If $s < q$, then it's your answer, stop. Else, go back to step $3$ and repeat.
Here's an image from Wikipedia, for the example of $q = 37$.
$$n^2 < 8n \log_2(n)$$
The inequality is false for $n=1$ and $n=2$
However, for $n \ge 3$ notice that $\frac{x}{\ln x}$ is an increasing function:
$$n < 8 \log_2(n)$$
$$\frac{n}{\log_2(n)} < 8 $$
We can then use bisection search to find such value
Best Answer
If you haven't already, you should prove that for all integers $k>0$, if you have an integer $N>0$ such that $2^{N}>N^{k}$, then, for all $n\geq N$, $2^{n}>n^{k}$ (or, more generally, there is an integer $N$ such that $2^{n}>p\left(n\right)$ for all $n\geq N$ where $p$ is any polynomial). This is a simple induction argument, and should be done in any algorithms course. From there, you set up the problem like so:
You're given that $8n^{2}<64n\lg n$. So, after a bit of algebra (you can do this part), we get it in to the form $2^{n}<n^{8}$. We have to find all $n>0$ such that this holds, and so, once we have found $N$ such that $2^{N}<N^{8}$ and $2^{N+1}\geq\left(N+1\right)^{8}$, we will know that all integers in the interval $1\leq n\leq N$ satisfy the problem. You can easily find $N$ with a calculator.
(Hint: $N$ is bigger than 40 but less than 45)