I'm currently working a few exam question, and got stuck at this point. I am given that a Quicksort algorithm has a time complexity of $O(nlog(n))$. For a particular input size, the time to sort the list is 4 minutes. The question proceeds to ask how long will it take to sort a list of twice the size, on the same system.

I have already ruled out the the time isn't 8 minutes (twice the input size = twice the duration, very very wrong reasoning).

Some working I did:

Working A)

  • $4 = nlog(n)$
  • $4 = log(n^n)$
  • $16 = n^n$
  • I got basically stuck at this point.

Working B)

  • $X = 2nlog(2n) >> 2n$ since double the input
  • $X = 2n(1 + log(n))$
  • $X = 2n + 2nlog(n) >> nlog(n)$ was 4 minutes
  • $X = 2n + 2(4) = 2n + 8$
  • I once again got stuck at this point.

Can't really figure out how to solve such a problem, really appreciate you help!

Best Regards.

  • $\begingroup$ FWIW, the question as asked doesn't have an exact answer because all you know is the asymptotic (big-$O$) behavior as $n \to \infty$. That's not enough for a numerical answer, but is enough for your instructor to know if you understand the question. $\endgroup$ Jan 31 '16 at 18:35

You have that the time taken to complete a task is $T=kn\log n$.

When $n=n_1$, the corresponding $T_1=kn_1 \log n_1$

You need to find $T_2=k(2n_1) \log (2n_1)$

$T_2=2kn_1 (\log 2 + \log n_1)$

$T_2=2kn_1 \log 2 + 2kn_1 \log n_1$

$T_2=2kn_1 \log n_1 \frac {\log 2}{\log n_1} + 2kn_1 \log n_1$

$T_2=2T_1 \frac {\log 2}{\log n_1} + 2T_1$

$T_2=2\left (\frac {\log 2}{\log n_1} + 1 \right )T_1$

So the time is a little more than doubled. Exactly how much depends on the size of $n_1$:

If $n_1=2$ (very unlikely), then $T_2=2\left (\frac {\log 2}{\log 2} + 1 \right )T_1 = 4 T_1 = 16$ minutes

If $n_1=4=2^2$ (still unlikely), then $T_2=2\left (\frac {\log 2}{\log 4} + 1 \right )T_1 =2\left (\frac {1}{2} + 1 \right )T_1 = 6 T_1 = 12$ minutes

If $n_1=8=2^3$ , then $T_2=2\left (\frac {1}{3} + 1 \right )T_1 = \frac 83 T_1 = 10$ minutes $20$ seconds

If $n_1=16=2^4$ , then $T_2=2\left (\frac {1}{4} + 1 \right )T_1 = \frac 52 T_1 = 10$ minutes

  • $\begingroup$ Got it. Can't understand how he asks for an "approximate value" in the question, because sufficient information simply isn't provided. Cheers! $\endgroup$ Jan 31 '16 at 18:42

We assume that the time consumption has reached the asymptotic behavior, that is that the time taken is actually $T(n) = T_0 n \log_2 n$.

With this assumption you're correct the double size will not result in double time, it will be more than that. However the ratio can be arbitrarily close to doubling. We have:

$$T(2n) = T_0 2n \log_2 (2n) = T_2 2n (\log_2 2 + \log_2 n) = 2T_0 n\log_2 n \left(1+{\log_2 2\over\log_2 n}\right) = 2T(n)\left(1+{1\over\log_2 n}\right)$$

Actually it's quite reasonable to think that $n$ is rather large given it takes four minutes to sort. So I'd say it's pretty close to $2T(n)$ that is eight minutes.

The understanding is not shown by your conclusion, but rather how you reach your conclution.


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.