# 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.

• 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).

• can we say it's O(s) ? – Karo Oct 11 '14 at 16:17
• No. $n$ can be larger than $s$ by any factor. – FrankW Oct 11 '14 at 16:26
• how can I prove that $O(s)$ is wrong ? can I use an array fill with $0$? so when we increase $n$ then s will be always 0. but we use just one example I think I should prove it for general case that $O(s)$ is wrong. is there any better proof? – Karo Oct 11 '14 at 16:53
• $O(s)$ means that there is a constant $c$, so that the runtime for every input (larger than some threshold) is bounded by $c\cdot s$. So to disprove this, you only need to show that for each $c$ there are arbitrarily large inputs that do not satisfy this relation. For an array full of zeroes $cs=s=0$, but the runtime is definitely larger than 0. Since there are arbitrarily large arrays full of zeroes, this is sufficient to disprove $O(s)$. – FrankW Oct 11 '14 at 20:13