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

Asymptotic analysis of a summation

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

Problem

I was calculating the time complexity of one of the phases of my proposed algorithm, but unfortunately, I faced a problem about solving that and providing an understandable running-time. This phase of the algorithm indeed iterates a task $t$ times where $t$ is that iteration in which the algorithm achieves the desire result (optimal value). Each iteration $i$, where $0\leq i\leq t$, runs in $O\big((Y-iy)(\log(Y-iy)+D-id)\big)$ such that $y$ is the expected amount by which $Y$ decreases and $d$ is also the expected amount by which $D$ decrease at each iteration $i$. Therefore the total time complexity of this phase is as follows:

$$\sum_{i=0}^t O\big((Y-iy)(\log(Y-iy)+D-id)\big)\,.$$

Now I would like to find a nice solution for that. Can you help me approximate this in order to obtain a better solution?
Any help will be appreciated. Thank you in advance.

Solution

Assuming all the quantities are positive, just use $\log(Y-iy)\leq \log Y$, expand the brackets and use the standard identities for $\sum_i i$ and $\sum_i i^2$. The $\log$ term disappears anyway since, asymptotically, it's dominated by the terms polynomial in $i$.

Context

StackExchange Computer Science Q#96573, answer score: 2

Revisions (0)

No revisions yet.