# Describing time complexity when internally using a function of unknown complexity

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$?

• "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?" Mar 30 '17 at 9:58
• @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 Mar 30 '17 at 10:12

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.
• 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? Mar 31 '17 at 9:23