A homework assignment asks me to state the complexity in Big-O notation of the function $$f(n) = 7n – 3n \log n + 100000 $$

I graphed this function and decreases all the way down to zero nearly its entire lifespan. Therefore I concluded that the complexity is bounded by a constant and has the complexity $O(1)$.

Is this correct?

Also out of curiosity, what is the Big-Omega of this function is? The best it could ever run is also O(1). What about Big-Theta? I'm having trouble getting my head around these.

  • $\begingroup$ a tricky one. did you think about $O(-n\log n)$? $\endgroup$
    – Ran G.
    Commented Mar 6, 2013 at 5:07
  • 2
    $\begingroup$ It does not just decrease to zero, it turns negative. $\endgroup$ Commented Mar 6, 2013 at 5:07
  • 1
    $\begingroup$ Are you talking about time complexity? $\endgroup$
    – Sid
    Commented Mar 6, 2013 at 5:18
  • 1
    $\begingroup$ @RanG. negative values is an odd case for Big-O. I don't think it's ever come up... But, carefully check all the definitions, if it's valid, then ok. $\endgroup$
    – Joe
    Commented Mar 6, 2013 at 5:27
  • 1
    $\begingroup$ See also our reference question. You have to get your definitions straight! Note also that there is no algorithm anywhere in sight here! Clearly, $f$ can not be the runtime function of any algorithm. Furthermore, see here regardings using plots in this context. $\endgroup$
    – Raphael
    Commented Mar 6, 2013 at 7:15

1 Answer 1


If you use suitable definitions, you'll find that your function is in

  • $O(2^n)$,
  • $O(n^4)$,
  • $o(1)$ and
  • $\Omega(-n^2)$,

among many others. It's likely that the question (implicitly) asks for sharper bounds; I'll leave that for you to figure out.


Your Answer

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

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