Assume that I have some functions $f$ and $g$, both implemented perfectly, where

$$ f(x, g(z)) = \sum_{k=0}^{k=\lfloor{x}\rfloor}g(k)\quad (x > 1)\,. $$

Function $g$ is of unknown definition. I would like to express the time complexity of $f$ in big-O notation. My initial thought was to do something similar to:

$$ O(\sum_{k=0}^{k=\lfloor{x}\rfloor}T_g(k))\,. $$

Assume $T_g$ represents the time function of function g. However, this representation feels inadequate and irreducible for asymptotic time complexity; there should be a better way to express $T_f$.

How do I describe, in big-O notation, the time complexity of $f$?

  • $\begingroup$ "In big-O notation" is essentially irrelevant. It's just notation. Just like "in Roman numerals" is essentially irrelevant in the question "What is 34+87 in Roman numerals?" $\endgroup$ Mar 30, 2017 at 9:58
  • $\begingroup$ @DavidRicherby Fair enough - but my question still remains to be about the time complexity of a function which contains an inner function of unknown complexity. I simply phrased the question very poorly. :P $\endgroup$ Mar 30, 2017 at 10:12

1 Answer 1


In complete generality there is nothing much you can say. However, in many circumstances it will be the case that $g(n)$ is monotone, and in that case you can say that $$ \sum_{k=1}^n g(k) \leq ng(n), $$ a bound which is often quite good.

  • $\begingroup$ So the idea is I take the maximum time complexity term of the sum and multiply it by n, and I know it will be less than that? $\endgroup$ Mar 31, 2017 at 9:23
  • $\begingroup$ Yes, that's the idea. $\endgroup$ Mar 31, 2017 at 11:06

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.