Determining run-time complexity

Ye' old general discussion board. Basically, for everything that isn't covered elsewhere. Come here to shoot the breeze, shoot your mouth off, or whatever suits your fancy.
This forum is not for asking programming related questions.

Moderator: General Moderators

Post Reply
User avatar
superdezign
DevNet Master
Posts: 4135
Joined: Sat Jan 20, 2007 11:06 pm

Determining run-time complexity

Post by superdezign »

This is fairly basic, but something that I am mathematically stuck on for my homework (yes, homework).

For the psuedocode:

Code: Select all

for(int i = 0; i < n; i++)
    for(int j = i; j <= n; j++)
        for(int k = i; k <= j; k++)
            sum++;
I am supposed to determine the how many times the last statement (line 4) is executed. n is an arbitrary variable that I must solve my answer in terms of. I'll explain my logic and, hopefully, someone can find my flaw or lead me in the right direction.

Line 4 executes only when k <= j. k ranges from i to j, inclusive. j ranges from i to n, inclusive. i ranges from 0 to n-1, inclusive.

Let's follow the process to find the pattern, starting with i = 0:
When i = 0, j ranges from 0 to n. k ranges from 0 to j.
Line 4 is called 1 time in loop 1, 2 times in loop 2, 3 times in loop 3, … up to n+1 times in the last loop.
When i = 1, j ranges from 1 to n. k ranges from 1 to j.
Line 4 is called 1 time in loop 1, 2 times in loop 2, 3 times in loop 3, … up to n times in the last loop.


This continues until i = n-1. The range of k decrements by 1 in each iteration of the loop on line 2. So, line 3 is executed 1 less time for each iteration of the loop on line 2. Since i does not range all the way to n, j and k will never start at n, meaning that that there will never be a time when lines 3 & 4 are only executed once in a loop. My equation at this point for the number of times that line 4 is run is as follows:

Code: Select all

T[size=70]4[/size] = (1+2+3+ … +(n-1)+n+(n+1)) + (1+2+3+ … +(n-1)+n) + (1+2+3+ … +(n-1)) + … + (1+2+3) + (1+2)
My assumption is that there are n terms in this equation. I am fairly certain that this is accurate, but where to go from this point is beyond me. I have tried two approaches:
  • factoring the terms by iterations, and
  • factoring the terms by common terms.
For the first approach, I just simplified the adding of consecutive integers into ½n(n+1) form:

Code: Select all

T[size=70]4[/size] = ½(n+1)(n+2) + ½n(n+1) + ½(n-1)(n) + … + ½(3)(4) + ½(2)(3)
T[size=70]4[/size] = ½[(n+2)(n+1) + (n+1)(n) + (n)(n-1) + … + (4)(3) + (3)(2)]
However, I'm not sure how to simplify it any further than that. If anyone knows of a technique, I'd appreciate it.

The other approach was to group like terms (i.e. (n+1), n, (n-1), etc):

Code: Select all

T[size=70]4[/size] = (n-1)(1) + (n-1)(2) + (n-2)(3) + (n-3)(4) + … + 5(n-3) + 4(n-2) + 3(n-1) + 2(n) + 1(n+1)
T[size=70]4[/size] = 1(n-1) + 2(n-1) + 3(n-2) + 4(n-3) + … + 5(n-3) + 4(n-2) + 3(n-1) + 2(n) + (n+1)
T[size=70]4[/size] = [1(n) + 2(n-1) + 3(n-2) + 4(n-3) + … + 5(n-3) + 4(n-2) + 3(n-1) + 2(n)] + (n+1) - 1
T[size=70]4[/size] = [(n+1) + 3(n) + 5(n-1) + 7(n-2) + 9(n-3) + …] - 1
But, again, I have no idea where to go from here.


Any help would be appreciated. ^^
Eric!
DevNet Resident
Posts: 1146
Joined: Sun Jun 14, 2009 3:13 pm

Re: Determining run-time complexity

Post by Eric! »

Have you tried a few numbers to make sure your formula works?
superdezign wrote:

Code: Select all

T[size=70]4[/size] = (1+2+3+ … +(n-1)+n+(n+1)) + (1+2+3+ … +(n-1)+n) + (1+2+3+ … +(n-1)) + … + (1+2+3) + (1+2)
I think summations might be better. I'm using the word SUM in place for the SIGMA symbol
(1+2+3+...+(n-1)+(n+1)) is SUM(n+1)

(1+2+3+ … +(n-1)+n) is SUM(n)

(1+2+3+ … +(n-1)) is SUM(n-1)

then add the constants. You could further simplify

SUM(n+1) + SUM(n)+SUM(n-1)+ 9
to
3*SUM(n) + 9

Anyway that's the math, but I'm not sure your expression is correct...I didn't check it. Run some numbers through it to test it. Now that I look at it, I don't think it is right because the equation says if n=0 line 4 should be run 9 times....
Eric!
DevNet Resident
Posts: 1146
Joined: Sun Jun 14, 2009 3:13 pm

Re: Determining run-time complexity

Post by Eric! »

F(x)=Σ(x*(x+1)/2) (as x=0 to x=n)

You can test it here:
http://www.math.sc.edu/cgi-bin/sumcgi/calculator.pl
as and example x=0 to x=10 use "sigma[0,10,k*(k+1)/2]"

Since you didn't try to solve g(x) I didn't really look at it because it is his homework after all. :D
Eric!
DevNet Resident
Posts: 1146
Joined: Sun Jun 14, 2009 3:13 pm

Re: Determining run-time complexity

Post by Eric! »

Oh, I see how you wrote it now. For x=n loops, sum=f(x+1)-1
or

sum=Σ(x*(x+1)/2) - 1 for (x=0 to n+1)

as and example where n=10, x=0 to x=10 use "sigma[0,11,k*(k+1)/2] - 1"
on
http://www.math.sc.edu/cgi-bin/sumcgi/calculator.pl

There isn't a closed form solution for this that I can see. You have to use a series summation to solve it.
User avatar
superdezign
DevNet Master
Posts: 4135
Joined: Sat Jan 20, 2007 11:06 pm

Re: Determining run-time complexity

Post by superdezign »

T4(n) = (1+2+...+(n-1)+n+(n+1)) + (1+2+...+(n-1)+n) + (1+2+...+(n-1)) + … + (1+2)
T4(n) = ½(n+1)(n+2) + ½n(n+1) + ½(n-1)(n) + … + ½(3)(4) + ½(2)(3)
T4(n) = ½∑(n+1)(n+2)
T4(n) = ½∑(n²+3n+2)
T4(n) = ½∑n² + (3/2)∑n + ∑1
T4(n) = ½(1/6)n(n+1)(2n+1) + (3/2)½n(n+1) + n
T4(n) = (1/12)n(n+1)(2n+1) + (3/4)n(n+1) + n

Converting to summation notation, then converting back was what I needed to do. Tyvm ~Eric! for the idea.
Eric!
DevNet Resident
Posts: 1146
Joined: Sun Jun 14, 2009 3:13 pm

Re: Determining run-time complexity

Post by Eric! »

Ok, so I have to check this now.
sum=f(x)=Σ(x*(x+1)/2) - 1 (where x=0 to x=n+1)

for x=n+1 transpose the equation
½∑(n+1)*(n+2) - 1
½∑(n²+3n+2) - 1
½∑n² + 3/2∑n + ∑ 1 - 1

(1/12)n(n+1)(2n+1) + (3/4)n(n+1) + n - 1

Now if it weren't for the -1 it would work.... I'll let McInfo figure that one out.

By the way, what are those summation transforms called where
∑n² = 1/6*n*(n+1)*(2n+1)

I searched for those all over the internet but couldn't remember what they were called (it's been 20+ years now)...so I gave up and left it in a summation.
User avatar
Eran
DevNet Master
Posts: 3549
Joined: Fri Jan 18, 2008 12:36 am
Location: Israel, ME

Re: Determining run-time complexity

Post by Eran »

By the way, what are those summation transforms called where
induction furmulas
User avatar
superdezign
DevNet Master
Posts: 4135
Joined: Sat Jan 20, 2007 11:06 pm

Re: Determining run-time complexity

Post by superdezign »

Eric! wrote:Now if it weren't for the -1 it would work...
There is no "- 1" in the equation. I'll explain this to confirm my thought process. :P

1+2+3+...+n equals ∑i from i=1 to n, which is equal to ½n(n+1).

So when we factor:

T4(n) = (1+2+...+(n-1)+n+(n+1)) + (1+2+...+(n-1)+n) + (1+2+...+(n-1)) + … + (1+2)

We get:

T4(n) = (∑i from i=1 to n+1) + (∑i from i=1 to n) + (∑i from i=1 to n-1) + … + (∑i from i=1 to 2)
T4(n) = (½(n+1)((n+1)+1)) + (½n(n+1)) + (½(n-1)((n-1)+1)) + … + (½(2)(2+1))
T4(n) = ½(n+1)(n+2) + ½n(n+1) + ½(n-1)(n) + … + ½(2)(3)

When we turn that into a summation, the first term is ½(2)(3) and the last term is ½(n+1)(n+2).

Our summation is ∑½(i+1)(i+2) from i=1 to n.
When i=1, the first term is ½(2)(3).
When i=n, the last term is ½(n+1)(n+2).

Then, we continue the algebra from there.
Eric! wrote:By the way, what are those summation transforms called where
∑n² = 1/6*n*(n+1)*(2n+1)
I dunno. ~pytrin does though. :P
Eric!
DevNet Resident
Posts: 1146
Joined: Sun Jun 14, 2009 3:13 pm

Re: Determining run-time complexity

Post by Eric! »

Induction formulas...now I can sleep again.

I think the -1 was a by product of going 0 to n+1 and I didn't transpose McInfos equation right. Because the summation form McInfo did works but you have to increase the index by one. I see what you did with the factoring better now and how I screwed up my attempt in the first post.
Post Reply