CODEWITHSUNDEEP
math
Linens
Linens

Reputation: 7942

How to analyze this pseudocode

I have the following pseudocode:

sum<-0
inc<-0
for i from 1-n
  for j from 1 to i
     sum<-sum+inc
     inc<-inc+1

I am asked to find a closed formula. The hint is to use common summations. No matter how I look at it I cannot write this code in summation form. Can someone give me an idea of what the summations would look like or even a recursive formula?

Upvotes: 0

Views: 655

Answers (2)

paxdiablo
paxdiablo

Reputation: 881323

Assuming the for i from 1-n means:

for i from 1 to n

A closed formula for that can be obtained through some numerical analysis. Let's examine the number of times through the loop for a couple of values of n (5 and 6).

The outer loop is always n times and the inner loop is whatever i is for each iteration, so for values of n, here are the iteration counts:

n    count
=    ===========================================
1    (1)                                    =  1
2    (1),(12)                               =  3
3    (1),(12),(123)                         =  6
4    (1),(12),(123),(1234)                  = 10
5    (1),(12),(123),(1234),(12345)          = 15
6    (1),(12),(123),(1234),(12345),(123456) = 21

The closed formula for these is best illustrated as follows:

n = 5: 5 + 4 + 3 + 2 + 1
       |   |   |   |   |
       |   |   V   |   |
       |   |   3   |   |  Formula is: (n+1)*((n-1)/2)  +  ((n+1)/2)
       |   +-> 6 <-+   |             [outer pair sets] + [inner value]
       +-----> 6 <-----+
              --
              15

This is a formula for all odd values of n. For even values, a similar method can be used:

n = 6: 6 + 5 + 4   +   3 + 2 + 1
       |   |   |       |   |   |
       |   |   +-> 7 <-+   |   | Formula is:   (n+1)*(n/2)
       |   +-----> 7 <-----+   |            [outer pair sets]
       +---------> 7 <---------+
                  --
                  21

This tells you the number of iterations of the nested loop for each value of n (we'll call this x).

The calculation of the final value of sum is very similar. On the first iteration you add zero. On the second iteration, you add one. On the third iteration, you add two. That's pretty much exactly the same thing you had to do to figure out the number of iterations, only now it's based on x rather than n and it's 0+1+2+... rather than 1+2+3+..., meaning we can use exactly the same formula just by applying it to x-1 rather than x.

So we can use:

if n is odd:
    x <- (n+1) * ((n-1)/2) + ((n+1)/2)
else:
    x <- (n+1) * (n/2)
x <- x - 1
if x is odd:
    sum <- (x+1) * ((x-1)/2) + ((x+1)/2)
else:
    sum <- (x+1) * (x/2)

Checking this against the algorithm for the first few values on n:

n  algorithm  formula
-  ---------  -------
0       0         0
1       0         0
2       3         3
3      15        15
4      45        45
5     105       105

So, a perfect match, at least withing the sample space chosen. You could actually go further and turn that into a single formula based on n alone rather than working out an intermediate value, but I'll leave that as an exercise for the reader.

Hint: A C formula which works for both odd and even numbers is:

    x <- ((n+1) * ((n-(n%2))/2)) + ((n%2) * ((n+1)/2))

(though still not tested for negative values of n - you should put a check for that before you use the formulaic version).

Upvotes: 1

user684934
user684934

Reputation:

Innermost loop (let's just call i a fixed number):

inc is incremented i times.
sum has inc added to it i times. (i*(i-1)/2, right?)

If we assume that inc and sum start art value 0, then that's valid. If we assume that they start at some different value, let's call them k and l, then we know that inc will end up at value k+i. We know that sum will end up at l+k*i + i*(i-1)/2.

Now, i itself is going from 1 to n. Um... hum. Let me think about this a bit more.

Upvotes: 0

Related Questions