Complexity of an Nested Loop (Recurrence Relation)

Question

Algorithm-1 (A:array[p..q] of integer)
    sum, max: integer
    sum = max = 0
    for i = p to q 
        sum = 0
        for j = i to q 
            sum = sum + A[j]
            if sum > max then
                max = sum
    return max

How many times does the nested loop execute?

I'm aware that the first for loop has an O(n) complexity, and that the whole algorithm has a total complexity of O(n^2). However, I need the exact number of executions of the inner loop in order to prove this via a recurrence relation.

lc. · Accepted Answer · 2012-11-01 02:21:36Z

1

Wouldn't it just be Sum(i = 1 -> n, i), which equals n(n+1)/2?

In your case, n = q-p+1, so you get (q-p+1)(q-p+2)/2.

Expanding this out - if I've done this right - you get (q^2-qp+2q-pq+p^2-2p+q-p+2)/2 = (q^2+p^2-2qp+3q-3p+2)/2.

answered Nov 1, 2012 at 2:21

lc.

117k21 gold badges163 silver badges190 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Karthik T · Accepted Answer · 2012-11-01 02:17:47Z

1

If you want an exact number, the inner loop is invoked (n + n-1+ ...1) = n(n+1)/2 ~= O(n^2)

Here n = q-p

answered Nov 1, 2012 at 2:17

Karthik T

32.1k7 gold badges71 silver badges92 bronze badges

Comments

Arun Manivannan · Accepted Answer · 2012-11-01 04:36:09Z

1

Probably not the answer you were looking for. In fact, you got it right that the inner loop has O(n) and the entire program has O(n^2) complexity. Just throw in a counter and increment it in your inner loop. That should give you the exact number of executions.

edited Nov 1, 2012 at 4:36

answered Nov 1, 2012 at 2:17

Arun Manivannan

4,3133 gold badges31 silver badges38 bronze badges

Comments

nmoses · Accepted Answer · 2012-11-01 02:53:24Z

0

The inner loop runs q-i+1 times and the total number of executions is

\sum{ i=p }^{ q } (q-i+1) = \sum{ k=1 }^{ q-p+1 } (k) = n * (n+1) /2

where n = q-p+1.

answered Nov 1, 2012 at 2:53

nmoses

635 bronze badges

Collectives™ on Stack Overflow

Complexity of an Nested Loop (Recurrence Relation)

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related