Time Complexity Calculation

Question

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.

Answer 1

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

Answer 2

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.