# Thread: Matlab - Determining the complexity of an algorithm

1. ## Matlab - Determining the complexity of an algorithm

Hey everyone

I'm trying to determine the complexity of the following algorithm:

Code:
A = 0:n;
for i = 0:n-1
s = 0;
for j = 1:i
s = s + X(j);
end

A(i+1) = s / (i+1);
end
I came up with the following:

$\displaystyle f(n) = \sum^{n-1}_{i = 0} \left( \left( \sum^{i}_{1} (1) \right) + 2 \right) + 1$

$\displaystyle f(n) = \sum^{n-1}_{i = 0} \left( i \right) + 2n + 1$

$\displaystyle f(n) = \left( n \right) + 2n + 1$

$\displaystyle f(n) = 3n + 1$

But something doesn't seem right here, since I've got a double for-loop. Shouldn't I be getting an $\displaystyle n^2$ ?

Also, I'm supposed to find the complexity of the algorithm theoretically and practically. What exactly is the difference between the algorithm on paper and after I've coded it? The instructions are exactly the same.

2. Originally Posted by janvdl
Hey everyone

I'm trying to determine the complexity of the following algorithm:

Code:
A = 0:n;
for i = 0:n-1
s = 0;
for j = 1:i
s = s + X(j);
end

A(i+1) = s / (i+1);
end
I came up with the following:

$\displaystyle f(n) = \sum^{n-1}_{i = 0} \left( \left( \sum^{i}_{1} (1) \right) + 2 \right) + 1$

$\displaystyle f(n) = \sum^{n-1}_{i = 0} \left( i \right) + 2n + 1$

$\displaystyle f(n) = \left( n \right) + 2n + 1$

$\displaystyle f(n) = 3n + 1$

But something doesn't seem right here, since I've got a double for-loop. Shouldn't I be getting an $\displaystyle n^2$ ?

Also, I'm supposed to find the complexity of the algorithm theoretically and practically. What exactly is the difference between the algorithm on paper and after I've coded it? The instructions are exactly the same.
$\displaystyle \sum_{i=0}^n i = \frac{n(n+1)}{2}$

CB

3. Originally Posted by CaptainBlack
$\displaystyle \sum_{i=0}^n i = \frac{n(n+1)}{2}$

CB
Since the upper bound is n-1 will the result then be as follows?
$\displaystyle \sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}$

4. Originally Posted by janvdl
Since the upper bound is n-1 will the result then be as follows?
$\displaystyle \sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}$
Yes.

If you prefer, you can view that this way :
$\displaystyle \sum_{i=0}^{k} i=\frac{k(k+1)}{2}$

Then let k=n-1

5. Thanks for the help CB and Moo

6. Originally Posted by Moo
Yes.

If you prefer, you can view that this way :
$\displaystyle \sum_{i=0}^{k} i=\frac{k(k+1)}{2}$

Then let k=n-1
I did simply subtitute it into the formula CB gave me. I don't have much experience with sequences and series. (I'm taking it next semester though.)