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.

  • 1
    $\begingroup$ $\sum O(\_)$ is not a very meaningful thing to write down. (see e.g. here) $\endgroup$ – Raphael Aug 24 '18 at 14:43
  • $\begingroup$ 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! $\endgroup$ – Raphael Aug 24 '18 at 14:43
  • $\begingroup$ Thanks to @Raphael. I will try to get better. $\endgroup$ – Nima Farnoodian 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$.

  • $\begingroup$ 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)$. $\endgroup$ – Nima Farnoodian Aug 26 '18 at 12:59
  • $\begingroup$ @NimaFarnoodian Yes, that’s clear. $\endgroup$ – David Richerby Aug 26 '18 at 15:45
  • $\begingroup$ 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. $\endgroup$ – Nima Farnoodian Sep 8 '18 at 21:03
  • $\begingroup$ 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. $\endgroup$ – Nima Farnoodian Sep 8 '18 at 21:16

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.