# Matlab - Determining the complexity of an algorithm

• Mar 19th 2009, 02:42 AM
janvdl
Matlab - Determining the complexity of an algorithm
Hey everyone (Hi)

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:

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

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

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

$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 $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.
• Mar 19th 2009, 03:35 AM
CaptainBlack
Quote:

Originally Posted by janvdl
Hey everyone (Hi)

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:

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

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

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

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

$\sum_{i=0}^n i = \frac{n(n+1)}{2}$

CB
• Mar 19th 2009, 03:39 AM
janvdl
Quote:

Originally Posted by CaptainBlack
$\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?
$\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}$
• Mar 19th 2009, 04:23 AM
Moo
Quote:

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

Yes.

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

Then let k=n-1
• Mar 19th 2009, 04:24 AM
janvdl
Thanks for the help CB and Moo (Clapping)
• Mar 19th 2009, 04:25 AM
janvdl
Quote:

Originally Posted by Moo
Yes.

If you prefer, you can view that this way :
$\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.)