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.
    Mar 6 '13 at 5:07
  • 2
    $\begingroup$ It does not just decrease to zero, it turns negative. $\endgroup$ Mar 6 '13 at 5:07
  • 1
    $\begingroup$ Are you talking about time complexity? $\endgroup$
    – Sid
    Mar 6 '13 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
    Mar 6 '13 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
    Mar 6 '13 at 7:15

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, privacy policy and cookie policy

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