3
$\begingroup$

I have a complex function, which looks something like this:

$$f(x) = \sum_{k=0}^x{\frac{g(k)}{h(k)}} + l(x)$$

Now, $g(k) = O(\log k)$ and $h(k) = O(k)$, the sum iterates $k$ from $0$ to the parameter $x$ and $l(x)$ is meant to provide a decimal correction, but its form is $\dfrac{a^{b-x}}{h(k)} (a,b - const)$.

How can I assess the big O of $f(x)$?

I did some calculations and came up with $O(x^2 \log x)$, but I'm not confident it is right.

$\endgroup$
3
$\begingroup$

I'm assuming you meant $l(x) = a^{b-x}/h(x)$, where $a \geq 1$. This term is $o(1)$ so can be ignored. For the main term, we cannot conclude anything since we only have an upper bound on $h$; we would like a lower bound on $h$. It could be, for example, that $g(k) = \log k$ and $h(k) = e^{-k}$, a function certainly satisfying $h(k) = O(k)$, and in that case $f(x) = \Omega(e^x)$.

Assuming you meant $h(k) = \Theta(k)$, or at least $h(k) = \Omega(k)$, we can estimate the sum using an integral: $$ \sum_{k=0}^x \frac{g(k)}{h(k)} = O\left(\sum_{k=0}^x \frac{\log k}{k}\right) = O\left(\int_0^x \frac{\log k}{k} dk\right) = O(\log^2 x),$$ using $\int \frac{\log k}{k} = \frac{1}{2} \log^2 k$. If $g(k) = \Theta(\log k)$ and $h(k) = \Theta(k)$ then $f(x) = \Theta(\log^2 x)$.

$\endgroup$
  • $\begingroup$ Yes, a >= 1 and (b-x) < 0. And h(k) = 3k+7, so it is literally a linear function. Could you please elaborate a little why is l(x) = O(1)? I'm confused by the denominator not contributing. For clarification purposes, would it still be O(1), if the second term was sum(k){l(k)} (similar to the first sum), instead just l(x)? $\endgroup$ – user3209815 May 17 '14 at 17:23
  • 1
    $\begingroup$ @user3209815 The denominator makes the expression smaller. First of all, $a^b$ is just a constant. If $a > 1$ then $a^{-x} = o(1)$, and since $h(x) = \Omega(1)$, we can conclude that $a^{-x}/h(x) = o(1)$. If you take a summation then you get $O(1)$ by summing the geometric series (again ignoring $h(x)$). $\endgroup$ – Yuval Filmus May 18 '14 at 5:37

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.