2
$\begingroup$

Suppose I have an algorithm that runs in $O(n)$ for every input of size $n$, but only after a pre-computation step of $O(n^2)$ for that given size $n.$ Is the algorithm considered $O(n)$ still, with $O(n^2)$ amortized? Or does big O only consider one "run" of the algorithm at size $n$, and so the pre-computation step is included in the notation, making the true complexity $O(n^2+n) = O(n^2)$?

$\endgroup$
2
  • 1
    $\begingroup$ I think you'll need to give us more details. What does the precomputation step depend on? If it doesn't depend on anything, then in the non-uniform model, you can precalculate the results of that precomputation and hardcode them in the algorithm itself. Read about non-uniform complexity to see about a subtlety in the definition of complexity: e.g., en.wikipedia.org/wiki/Circuit_complexity#Uniformity; en.wikipedia.org/wiki/P/poly. $\endgroup$ – D.W. Feb 22 '17 at 22:59
  • $\begingroup$ I was imagining it depended on $n$, but not any particular input of size $n.$ Like pre-computing a powerset of indices for an array of size $n$ $\endgroup$ – amoffat Feb 22 '17 at 23:05
4
$\begingroup$

I understand that you have some computational problem with input size $n$, and you use $f(n)$ time for preprocessing. Perhaps after that, you can answer some kind of queries in $g(n)$ time. Both $f$ and $g$ are functions of the input size, and you can now apply Big Oh and say, for instance, that $f(n) = O(n^2)$ and $g(n) = n$.

Now, nobody is forcing you to "consider the runtime to be $O(n)$" or anything like that. So why not just say it like it is, e.g., "after a $O(n^2)$-time preprocessing step, queries can be answered in $O(n)$ time", or "there is an $O(n^2)$-time algorithm for solving the problem", or whatever it is precisely that holds. It's up to you how you present it.

In particular, I want to clear the misconception that "big O would consider one 'run' of the algorithm". If you look at the definition of Big Oh, you'll see that it says nothing about algorithms or their "runs".

$\endgroup$
0
$\begingroup$

When you write about "the complexity", you must write exactly what you are measuring.

In your example, the time for solving one single problem of size n is $O (n^2)$ (actually, it could be better if there is an algorithm that doesn't do the reusable pre-computation and is faster than $O (n^2)$).

The time for solving k problems of size n is $O(n·max(k,n))$. I would say it is very similar to amortized time, but not exactly the same.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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