# What are the asymptotic bounds (upper bound on time complexity) of the following function?

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.

• Thank you all for your insights. I edited the explanation. Hope, it is more clear now. – mehdi Apr 5 '19 at 13:02
• 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. – ryan Apr 5 '19 at 14:21
• (1) I am looking for complexity of calculating $Q(t)$ for all $t$. – mehdi Apr 5 '19 at 15:41