I am trying to find the upper bound on time complexity of the recursive function defined by the following equation: $$Q(t) = \sum^{N}_{i=1} q_i \big(g_i^{\frac{1}{m-1}} + Q(t+1)^{\frac{m}{m-1}}\big)^{\frac{m-1}{m}}\quad \forall\, t = 1, \ldots,T-1.$$ Here, $0\leq q_i\leq 1$ are probabilities where $\sum^{N}_{i=1}q_i = 1$. Also, $g_i$ and $Q(t)$ are real valued numbers ($Q(T)=0$). I should mention that Im interested in complexity with respect to $N$ and $T$ (since I find complexity analysis with respect to $m$ very hard). From my understanding the term inside the summation, i.e., $$q_i \big(g_i^{\frac{1}{m-1}} + Q(t+1)^{\frac{m}{m-1}}\big)^{\frac{m-1}{m}}$$ can be considered as a constant time complexity operation since it does not depend on $T$ or $N$. Since, the term inside the summation is calculated $N$ times and for $t = 1, \ldots, T-1$, then the time complexity is $O(NT)$

I need help in verifying this.

  • 1
    $\begingroup$ Thank you all for your insights. I edited the explanation. Hope, it is more clear now. $\endgroup$
    – mehdi
    Commented Apr 5, 2019 at 13:02
  • $\begingroup$ Are you looking for (1) the asymptotic complexity of calculating this function $Q(t)$ for all $t$ or (2) the asymptotic complexity of this function $Q(t)$ for all $t$? If it is (2), then your assumption would be incorrect due to the recursive call to $Q(t + 1)$. Expanding it out, you would see it has a recursive branching factor of $N$, due to calling $Q(t+1)$ a total of $N$ times. $\endgroup$
    – ryan
    Commented Apr 5, 2019 at 14:21
  • $\begingroup$ (1) I am looking for complexity of calculating $Q(t)$ for all $t$. $\endgroup$
    – mehdi
    Commented Apr 5, 2019 at 15:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.