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)$.


4 Answers 4


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)$.


Yes. That is correct.

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

  • $\begingroup$ I submitted a paper to a journal with this explanation but the reviewer didn't accept it! $\endgroup$
    – M a m a D
    Jul 10, 2022 at 11:18
  • $\begingroup$ Just to clarify let's consider the following algorithm. Given an instance $x$ of size $n$, (i) apply a linear-time preprocessing step to $x$ to get a related instance $y$ of size $m=O(\sqrt{n})$, and (ii) solve $y$ using a subroutine with quadratic time-complexity. The running time of this algorithm (as a function of the size $n$ of the original instance $x$) is $O(n + m^2) = O(n + (\sqrt{n})^2) = O(n)$. The time complexity of the inner subroutine (as a function of the size of its input) is obviously unchanged, i.e., it is quadratic. Could this be the source of confusion? $\endgroup$
    – Steven
    Jul 10, 2022 at 12:46
  • $\begingroup$ @MamaD: you should have said it in the first place. And probably you did not use this exact exaplanation. $\endgroup$ Jul 11, 2022 at 20:07

Undisputably, the global time is

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

  • $\begingroup$ The algorithm took O(n^2) for uncompressed data. Nothing says it will be O(n^2) for compressed data. $\endgroup$
    – gnasher729
    Jul 12, 2022 at 9:07
  • 1
    $\begingroup$ @gnasher729: nothing more being said, one can infer that these are worst-case complexities and $O(n^2)$ always holds. $\endgroup$ Jul 12, 2022 at 9:19
  • $\begingroup$ The size of the input is smaller, but the number of operations is the same. So the number of operations as a function of the input size changes. $\endgroup$
    – gnasher729
    Jul 12, 2022 at 12:51

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.

  • $\begingroup$ It is implicit that the algorithm remains the same on "compressed data". So if the array size if reduced from $n^2$ to $n$, the number of diagonal elements drops from $n$ to $\sqrt n$. You are cheating by changing the nature of the algorithm, a diagonal is not an array. $\endgroup$ Jul 12, 2022 at 9:24
  • $\begingroup$ That's not what I described. The algorithm had a sqrt(n) by sqrt(n) matrix, but ignored all but the diagonal elements, and calculated a result from the diagonal elements alone. This takes n^2 steps with sqrt(n) diagonal elements. If the compression throws away everything but the diagonal elements, then the original algorithm cannot be used unmodified, but we can still do the exact same calculation for the sqrt(n) diagonal elements. Which will take the same n^2 operations. $\endgroup$
    – gnasher729
    Jul 12, 2022 at 12:49
  • $\begingroup$ Your reasoning is wrong - or does not respect the conditions of the question. The result of the "compression" must be a smaller matrix. $\endgroup$ Jul 12, 2022 at 13:25
  • $\begingroup$ If you read the comments, he submitted a paper and your argument was rejected. $\endgroup$
    – gnasher729
    Jul 14, 2022 at 4:51
  • $\begingroup$ You mean his argument, don't you ? I did not take part to the submission. Also see my last comment in Steven's post. $\endgroup$ Jul 14, 2022 at 6:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.