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 Apr 5 '19 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 Apr 5 '19 at 14:21
  • $\begingroup$ (1) I am looking for complexity of calculating $Q(t)$ for all $t$. $\endgroup$ – mehdi Apr 5 '19 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.