1
$\begingroup$

I was given this function: $T(N) = 3N\log^2 N + 5N^2\log N + \log N + 17N + 2$ and was asked to find the average Big O complexity.

If the Big(O) deals with an upper bound, would this algorithm be $O(N^2\log N)$ on average? But, because Big O is an upper bound, couldn't this also be $O(N^3)$, $O(N^4)$, etc.? Basically, is there a difference between Big O complexity and average Big O complexity of an algorithm?

$\endgroup$
  • 2
    $\begingroup$ There is no such thing as "average Big O complexity". It seems like a typo. $\endgroup$ – Yuval Filmus Mar 26 '17 at 10:15
  • $\begingroup$ Either you misunderstood something, or the person writing up the problem is confused. See also here. $\endgroup$ – Raphael Mar 26 '17 at 11:27
2
$\begingroup$

Strictly speaking, there are no such things as "Big O complexity" or "average Big O complexity". Look at the definition of Big Oh and you can stop guessing.

The right mindset is that you can analyze whatever aspect (say, the number of steps taken by an algorithm) in some case you care about (say, in the worst case, however you define it). You write a function $f$ of the input size $n$ that captures this. You do not need to know anything at all about asymptotic analysis up to this point. Now you can look at the definition of Big Oh again, and express $f(n)$ as the Big Oh of something.

With that being said, I think the questioner should clarify the meaning of "average Big O complexity". Concepts should not be intuitive and come out of thin air, but have precise definitions.

$\endgroup$
0
$\begingroup$

I agree with @Juho in that there is no average Big $O$ concept. Big $O$ is purely an upper bound for the time needed by the algorithm to process the whole input.

What you might have is an amortized cost, which tells you the average performance of each operation in the worst case.

Furthermore, of course you can say that $n = O(2^n)$ but this is a very weak upper bound.

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