Big O understanding given different input sizes

Question

I have a question about big O notation. Let's say I have 3 algorithms which, for an input of size $n$, have time complexity $O(n)$, $O(n^2)$ and $O(n \log n)$, respectively. Assume that all 3 algorithms take $a$, $b$ and $c$ seconds for the worst, average and best cases given an input of size $n$. What could be the actual time of these 3 algorithms given an input of size $2n$? Based on my understanding it should be:

• $O(n)$: $2a$, $2b$, and $2c$.
• $O(n^2)$: $a^2$, $b^2$, and $c^2$.
• $O(n \log n)$: $a \log a$, $b \log b$, and $c \log c$.

My questions are:

• Is this correct?
• In case not, why?
• In case this is correct, would the same hold for $\Theta$ and $\Omega$?

Answer 1

No, this isn't correct, for a number of reasons.

1. $O(\cdot)$ only gives upper bounds. Being told that $f(n)=O(n\log n)$ doesn't exclude the possibility that $f(n)=n$, $f(n)=1$, etc.

2. The bounds only apply to sufficiently large $n$. Perhaps your measurements were for values of $n$ that are too small to exhibit the asymptotic behaviour.

3. Even if $n$ was large enough, consider the algorithm "If my input has odd length, return immediately; otherwise, perform some calculation that takes exactly $n^2$ steps." This has running time $O(n^2)$, so you'd expect an input twice as big to take four times as long. But an odd-length input will take about $n$ steps, whereas $2n$ is even, so an input of that length would take time at least $(2n)^2$, which is much more than four times as much.

4. The actual running time of the code on an actual computer will depend on all kinds of factors that aren't included in the theoretical analysis. You could be careful to exclude things such as interruptions by other processes, but consider something like disc access. Suppose that your input of size $n$ takes up a quarter of a disc block. Most of the running time of your algorithm might be waiting for that one block to be transferred; the input of length $2n$ will also fit in one block, so you do the same amount of disc I/O and doubling the input takes only a small fraction longer to run. On the other hand, if your length-$n$ input is a whole block, then reading two blocks will take twice the time. Except that the OS will probably cache the second block for you, so probably it won't. Similar effects apply to memory accesses and their interaction with the cache.

5. Your arithmetic is off. Consider the three functions $f(n)=n$, $g(n)=n^2$ and $h(n)=n\log_2 n$. Then $$f(2n)=2n=2f(n)\\ g(2n)=(2n)^2=4n^2=4g(n)\\ h(2n)=2n\log_2 2n = 2n(\log_2 n+\log_2 2) = 2h(n)+2n\,.$$