1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ can we say it's O(s) ? $\endgroup$ – Karo Oct 11 '14 at 16:17
  • $\begingroup$ No. $n$ can be larger than $s$ by any factor. $\endgroup$ – FrankW Oct 11 '14 at 16:26
  • $\begingroup$ 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? $\endgroup$ – Karo Oct 11 '14 at 16:53
  • $\begingroup$ $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)$. $\endgroup$ – FrankW Oct 11 '14 at 20:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.