# big O of a complex function

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.

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)$.
• @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)$). – Yuval Filmus May 18 '14 at 5:37