# Asymptotic analysis of a summation

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.

• $\sum O(\_)$ is not a very meaningful thing to write down. (see e.g. here)
– Raphael
Aug 24 '18 at 14:43
• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Aug 24 '18 at 14:43
• Thanks to @Raphael. I will try to get better. Aug 24 '18 at 15:13

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$.
• Thank you for your follow up and answer. I did the same thing as you suggested, but I think if I find an upper bound for $t$ which is constant, I can say the algorithm runs in $O\big((Y)(\log(Y)+D)\big)$. Aug 26 '18 at 12:59
• Hi again. I tried to find a more understandable running time in order to give a better insight into this phase speed. To do so, I first an upper bound for $t$ and also simplified the running time replacing a more known variable with $D$. Could you please check that whether or not it's logically true. Please see the following comment. Sep 8 '18 at 21:03
• The real running time of this phase is $\sum_{i=1}^t O\big(Yi\log(Yi)+Mi)\big)\,$ where $Yi≤Yj$ and $Mi≤Mj$ for $i>j$, and $Y1=Y$. (Recall that the $M$ decreases as $Y$ decreases). Considering $Yi≤Y<n$ and $Mi≤m$ for all $i≤t$, $TC=O\big(t.(Y\log(Y)+m))\big)$. In proposition 1 ,$t$ is proved to be asymptotically $O\big(\log(n)\big)$. Since $m$ dominates $Y logY$, the worst-case running time of this phase is asymptotically $O(m\log(n)).$ Is this Logically true? I think this could be a clear upper bound that can make the further calculations simple. Sep 8 '18 at 21:16