Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
