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

Improve this question
$\endgroup$
2
  • $\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$ Commented 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$ Commented Mar 30, 2017 at 10:12

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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$ Commented Mar 31, 2017 at 9:23
  • $\begingroup$ Yes, that's the idea. $\endgroup$ Commented Mar 31, 2017 at 11:06

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.