# Calculate the average Big O from a function?

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?

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

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.
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.
Furthermore, of course you can say that $n = O(2^n)$ but this is a very weak upper bound.