CODEWITHSUNDEEP
pythonalgorithmcomplexity-theorybig-otime-complexity
Dennis Ritchie
Dennis Ritchie

Reputation: 640

Is my algorithm a linear time

# given an array, it solves sum of elements in it, 
# args: array, initial and final indices
# Returns: sum of elements
def ArrayTot (arr, low, high):
    return sum( arr[low : high+1] )

# Is this linear time?
# args: array, initial and final indices
# returns: Max possible value in sub-array.
def MaxSubArray (arr, low, high):
    # max value of sub-array
    TotalArray = 0
    # starts iterating arr from left - right i.e., arr[low, j]
    for j in xrange(low, high+1):
        # finds sum of sub array arr[low,j]
        tot = ArrayTot (arr, low, j)
        # Iterates the sub-array arr[low,j] so as to find any other possible arr[i,j] which results max value
        for i in xrange(low, j+1):
            SubArrTot = ArrayTot(arr, i, j)
            if SubArrTot >= tot:
                tot = SubArrTot
        if tot >= TotalArray:
            TotalArray = tot
    return TotalArray

arr = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]
low = 0
high = 15

print MaxSubArray(arr, low, high)

I am learning algorithms (Book: Introduction to Algorithms).. So, I am supposed to find a sub-array in a given array which constitutes maximum sum.. Yeah, a Non-recursive, linear time algorithm..

This is what I have done (shown above).. But In my solution, there is a for loop inside a for loop and both iterates 'n' terms..

If I am not wrong, it should be O(n^2) which is not linear! In that case, how should I probably solve it?

Upvotes: 0

Views: 603

Answers (2)

Marcus
Marcus

Reputation: 6849

I am afraid that it is not even 0(n^2).. it is O(n^3). ArrayTot(arr, i, j) is O(n), and it is in the i-loop which is inside the j-loop.

But you can optimize ArrayTot(arr, i, j) to O(1) by using a sum array, namely, range_sum[1..n], where range_sum[1] = arr[1], range_sum[i+1] = range_sum[i] + arr[i+1], i>0, then we can calculate ArrayTot(arr, i, j) in O(1) time, just use range_sum[j]-range_sum[i-1].

But you still cannot get O(n) with your method, this is a very classic DP problem, just google it.

Upvotes: 2

Qnan
Qnan

Reputation: 3744

This is certainly not a linear solution. One of the linear-time algorithms that solve this problem is known as the Kadane's algorithm.

Even just this bit of code 

for j in xrange(low, high+1):
    tot = ArrayTot (arr, low, j)

already has Theta(n^2) time complexity.

Upvotes: 5

Related Questions