Order of a pseudo code I am trying to find order of an bellow algorithm but I have no idea about, the problem like below

we have an array of $n$ element name $T[1...N]$ and we have that $0\leq T[i] \leq i$ and $T[i] \in \mathbb{Z}$ then if we have that $\sum_{i=1}^{n}T[i] = s$ what will be the order of following pseudo code

K := 1
for i = 1 to n do
    for j = 1 to T[i] do
        K := K + T[i]


I should prove it, but I just don't know what should I prove. is it $O(s)$ or $O(n+s)$ or $O(n)$ ? between these three one I need best guess. I just need some suggest to solve this. thanks

First I was thinking that it's $O(s)$ but if $T[i] = 0$ for $1 \leq i \leq n$ then then it should be $O(n)$. after that one of my friend said in fact $s = \frac{n (n + 1)}{2}$ so when we say that it's $O(s)$ in fact it's $O(n^2)$ so that the better answer is $O(s)$ because for some examples $O(n)$ is wrong, for example when $T[i] = i$ for all $i$. I think $O(s)$ should be right answer.
First note that $s \le \frac{n(n-1)}2$, equality need not necessarily hold.

Your observations are all correct:


The addition (and the head of the inner loop) is executed $O(s)$ times.
The head of the outer loop  is executed $O(n)$ times.
Neither $s\in O(n)$ nor $n \in O(s)$ holds for all possible inputs.


In this situation, there are multiple ways to give a bound that holds for all inputs:


You can use the fact that $s \in O(n^2)$ and give $O(n^2)$ as a bound for the algorithm,
you can say that the runtime is in $O(\max\{n,s\})$, or
you can say that the runtime is in $O(n+s)$.


Note that the latter two statements are acually equivalent (i.e. $O(\max\{n,s\})$ and $O(n+s)$ describe the same set of functions).