2
$\begingroup$

Apologies for this simple question. I found it in the book Algorithms by Sedgewick and Wayne.

Give a formula to predict the running time of a program for a problem of size N when doubling experiments have shown that the doubling factor is $2^b$ and the running time for problems of size N0 is T.

$$ \frac{T(2N)}{T(N)}=2^b.$$

$$ T(N_0)=T. $$

I am not sure how to proceed after that.

$\endgroup$
0
$\begingroup$

Instead of solving the question for you, let me show you what steps you need to take in order to solve this problem on your own.

Suppose that $T(1) = T_0$ and $T(2n) = C T(n)$ for all $n$.

  • What is $T(2)$? What is $T(4)$? What is $T(8)$? What is $T(2^k)$?

Now suppose that $T$ is monotone: $T(n_1) \leq T(n_2)$ whenever $n_1 \leq n_2$.

  • If $2^k \leq n \leq 2^{k+1}$, what can you say about $T(n)$?
  • Can you now deduce the asymptotic rate of growth of $T(n)$ for arbitrary $n$?
$\endgroup$
  • $\begingroup$ I can guess that it is $(N/N_0)^b$ but not too sure how to write a sequence of equations to show it. $\endgroup$ – johnson Dec 25 '17 at 15:09
  • $\begingroup$ Try working on it for a few hours. That's the only way to learn. $\endgroup$ – Yuval Filmus Dec 25 '17 at 15:11
  • $\begingroup$ You asked "what can you say about T(n)?". I'm not sure what else to say besides it is $\ge T(2^k) and \le T(2^{k+1})$ $\endgroup$ – johnson Dec 25 '17 at 15:26
  • $\begingroup$ I'm not sure how to find the answer for n which is not a power of 2 $\endgroup$ – johnson Dec 25 '17 at 15:28
  • $\begingroup$ It's in fact impossible, given just your recurrence formula. But you can find the asymptotic rate of growth ("big Theta", which is a stronger form of "big O"; see cs.stackexchange.com/questions/57/…) assuming that $T$ is monotone. $\endgroup$ – Yuval Filmus Dec 25 '17 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.