HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

big O of a complex function

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
bigfunctioncomplex

Problem

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.

Solution

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)$.

Context

StackExchange Computer Science Q#25826, answer score: 3

Revisions (0)

No revisions yet.