CODEWITHSUNDEEP
algorithmpseudocode
WhyAyala
WhyAyala

Reputation: 675

Expressing pseudo code as a function of n

I want to express what this pseudo code returns as a function.

function mystery(n)
    r := 0
    for i:= 1 to n-1 do
        for j:= i+1 to n do
            for k:= 1 to j do
                r:= r+1
    return r

I believe it may be something along the lines of f(n) = n*(n-1)^2 but I don't think that's quite right. Can some one explain if this is correct and if false then how should I go about arriving to a proper answer.

Upvotes: 0

Views: 1583

Answers (1)

tskuzzy
tskuzzy

Reputation: 36456

Compute the function one loop at a time:

for k:= 1 to j do
    r:= r+1

Call this function K(j). It should be pretty obvious that K(j) = j.

Now let's go out one loop:

for j:= i+1 to n do
    r:=r+K(j)

Call this function J(i). Doing a bit more work, you should see that J(i) = (i+1) + (i+2) + ... + n. There's a mathematical formula for this kind of sum (I'll leave it up to you to figure this one out).

Now finally, the last loop:

for i:= 1 to n-1 do
    r:=r+J(i)

And then you do a little more work here to get your final answer.

Upvotes: 1

Related Questions