What happens to the running time if we reduce the size of input?

Question

Let there is an algorithm whose running time is $O(n^2)$. Suppose we apply a preprocessing step on the algorithm in $O(n)$ so that it reduces the input size to $O(\sqrt{n})$ but doesn't effect the true answer of the algorithm. It is just for optimization. Now is it true to say that the running time of the algorithm is $O(n)$ when preprocessing is applied? Because $O(n^2)$ becomes $O(\sqrt{n}^2)$ which is $O(n)$.

Answer 1

TL,DR: it's not the same $n$. That's where the confusion comes from.

When we say that an algorithm's complexity is $O(f(n))$ (i.e. $O(n)$ or $O(n^2)$ or whatever), it's implicit that $n$ is the size of the input. There is an implicit assumption here that there is a single numerical parameter that is “the size of the input” and that everyone agrees on what it is. (At least we have to agree up to what can be distinguished with asymptotic approximations — for example a length in bits vs a length in bytes doesn't matter since $O(f(8n))$ is the same thing as $O(f(n))$ for the kind of functions $f$ we tend to encounter in practice, such as polynomials.)

To be rigorous, we shouldn't say, for example, that a quadratic algorithm has running time $O(n^2)$, but that it has running time $O(n \mapsto n^2)$. What matters is the function, not the letter used in the description of the function. $O(n \mapsto n^2)$ is the same thing as $O(p \mapsto p^2)$ is the same thing as $O(z \mapsto z^2)$. (“$n$”, “$p$” and “$z$” respectively are bound variables in this notation.)

When you're dealing with multiple algorithms, the complexity of each algorithm may be expressed in terms of different parameters: it's not the same $n$ anymore. For example, if you chain algorithm A1 with algorithm A2 (i.e. the output of A1 is the input of A2), it's natural to express the complexity of A1 in terms of its input, and the complexity of A2 in terms of its input. So let $n$ be the size of the input to A1: the complexity of A1 is $O(f_1(n))$. And let $p$ be the size of the input to A2: the complexity of A2 is $O(f_2(p))$. That's not $O(f_2(n))$, since now we're calling $n$ the size of the input to A1, not the size of the input to A2. With a more formal notation, the complexity of A1 is $O(f_1)$ and the complexity of A2 is $O(f_2)$ — we get rid of that troublesome undefined “$n$”.

In your example, we apply a first algorithm A1 which, when given an input of size $n$, produces an output of size at most $\sqrt{n}$. You don't say what the complexity of this algorithm is. I'm going to assume that it runs in linear time, i.e. $O(n)$. Then we apply a second algorithm A2 whose running time is quadratic, i.e. $O(p \mapsto p^2)$. If we want to express the running time of A2 as a step in the composition {A1;A2} for an input of size $n$, we note that the running time of this step is $O(p^2)$ where $p$ is the size of the input to A2, and we know that this size is at most $\sqrt{n}$. Therefore the running time of the second step, expressed in terms of the original input size, is $O((\sqrt{n})^2) = O(n)$. Again assuming that the running time of A1 is $O(n)$, the total running time of {A1;A2} is $O((\sqrt{n})^2 + n) = O(n + n)$ which by the properties of $O$ is $O(n)$.

Answer 2

Yes. That is correct.

Also, I think that "yes/no" questions are discouraged.

Answer 3

Undisputably, the global time is

$$O(n)+O((c\sqrt n)^2)=O(n).$$

Answer 4

The question is: How long does it actually take to solve the problem given the compressed data as the input?

Let’s say your original problem takes a square matrix with n elements as it’s input (that is sqrt(n) rows and columns) and your algorithm calculates a function of the diagonal in O(n^2). If you compress your matrix to sqrt(n) by throwing all the non-diagonal elements away, the algorithm still takes O(n^2). Except because of the reduced problem size, for data with size s the time is now O(s^4).

Here’s your problem. You have an algorithm that works in O(n^2) for highly redundant data of size n. After you dramatically reduce the problem size, you have no redundancy left. It is highly unlikely that your algorithm runs in O(s^2) for the instance of size s without redundancy.

Maybe you should give an actual example. I gave one where the time goes up from $O(n^2)$ to $O(n^4)$.

Here's a different situation: Your input is n items, of which k are > 0. The output is a function of the k positive items and is found in $O (k^2)$, once the positive items are known. This is also $O (n^2)$. If you remove all items <= 0 in O (n) then the time will be $O(n + k^2)$ in total. This will be O(n) in cases where the number of positive items is $O(n^{1/2})$ but not otherwise, say if half the items are positive.