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$David Richerby– David Richerby2017年03月30日 09:58:41 +00:00Commented 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$Addison Crump– Addison Crump2017年03月30日 10:12:37 +00:00Commented 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$Addison Crump– Addison Crump2017年03月31日 09:23:37 +00:00Commented Mar 31, 2017 at 9:23 -
$\begingroup$ Yes, that's the idea. $\endgroup$Yuval Filmus– Yuval Filmus2017年03月31日 11:06:34 +00:00Commented Mar 31, 2017 at 11:06