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:
- $4 = nlog(n)$
- $4 = log(n^n)$
- $16 = n^n$
- I got basically stuck at this point.
- $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!