1
$\begingroup$

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

$\endgroup$
  • $\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$ – David Richerby Mar 30 '17 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$ – Addison Crump Mar 30 '17 at 10:12
3
$\begingroup$

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.

$\endgroup$
  • $\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$ – Addison Crump Mar 31 '17 at 9:23
  • $\begingroup$ Yes, that's the idea. $\endgroup$ – Yuval Filmus Mar 31 '17 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.