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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$?
Improve this answer
$\endgroup$
14
  • $\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
    Commented Dec 25, 2017 at 15:09
  • $\begingroup$ Try working on it for a few hours. That's the only way to learn. $\endgroup$
    – Yuval Filmus
    Commented Dec 25, 2017 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
    Commented Dec 25, 2017 at 15:26
  • $\begingroup$ I'm not sure how to find the answer for n which is not a power of 2 $\endgroup$
    – johnson
    Commented Dec 25, 2017 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
    Commented Dec 25, 2017 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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