CODEWITHSUNDEEP
pythonalgorithmbig-o
user3238920
user3238920

Reputation: 21

Determining runtime complexity

I'm trying to determine the runtime complexity of an algorithm that I have written to take an array and determine the length of the longest continuous subsequence of the array where the difference in the max and min of the subsequence is less than or equal to some given value.

The code

input = [16,19,20,22,27,23]
compareValue = 3
tmp,length = 0,0
for i in range(0,n):
  newArray = []
  for j in range(i,n):
      newArray.append(input[j])
      if abs(max(newArray) - min(newArray)) <= compareValue:
          tmp = len(newArray)
      else:
           if tmp > length
               length = tmp

the output from this this example would be 3

I've tried determining this on my own by reading examples on Big-O, but I'm not 100% certain as to the exact complexity and would really appreciate some clarification.

Edit: From what've read I think this runs in O(n^2), but again, I am not completely sure

Upvotes: 2

Views: 194

Answers (1)

ndpu
ndpu

Reputation: 22561

You have 2 loops. Suppose that number of elements is 5. Second loop iterations will be decreasing by 1 on each parent loop iteration:

outer loop iteration : * * * * *
inner loop iterations: 5 4 3 2 1

By summing second (or inner) loop iterations you can calculate overall number of 'operations' or complexity. And you have here simple summ of natural numbers from 1 to n (5). And formula for that summ is:

n * (n + 1) / 2 or (n^2 + n) / 2

at last in your inner loop on every iteration you are adding element to newArray and calling min and max on it. Complexity of both min and max is O(n) but length of array decreasing:

min,max for j in 0-4: 2 * (O(1)+O(2)+...+O(5))
min,max for j in 0-3: 2 * (O(1)+O(2)+...+O(4))
min,max for j in 0-2: 2 * (O(1)+O(2)+...+O(3))
min,max for j in 0-1: 2 * (O(1)+O(2)+...+O(2))
min,max for j in 0 : 2 * O(1)

and overall complexity will be summ: O(n^2 + n) + O((n-1)^2 + (n-1)) + ... O(1)

I think that roughly complexity of both min+max is O(2*n/2) or just O(n), so overall will be:

(n^2 + n) / 2 * (n) or (n^3 + n^2) / 2

or O(n^3)

Upvotes: 3

Related Questions