CODEWITHSUNDEEP
pythonarrays
AkifObaidi
AkifObaidi

Reputation: 17

Minimum Absolute Difference in an Array

Hi I have Solved this Minimum Absolute Difference in an Array problem with this Solution:

min_diff = 99999999
difference = 0  

for i in range(len(arr)):
    for y in range(len(arr)):
        if i != y:
            defference = abs(arr[i] - arr[y])
            if defference < min_diff:
                min_diff = defference
                
return min_diff

so as you can see my solution is O(n2) and it is giving a Time limit exceeded error so I have copied another solution which is this :

arr = sorted(arr)

# Initialize difference as infinite
diff = 10**20

# Find the min diff by comparing adjacent
# pairs in sorted array
for i in range(n-1):
    if arr[i+1] - arr[i] < diff:
        diff = arr[i+1] - arr[i]

# Return min diff
return diff

so as you can see it is the same as my code with time complexity so why this good is working correctly I didn't get the Time limit exceeded error. Please tell me what is the difference between my code and the code I have copied.

Upvotes: 0

Views: 285

Answers (1)

gog
gog

Reputation: 11347

One easy way to think about O(n) estimates is to count how many nested loops you have. Your code has two loops, so it is "quadratic" and would require 100^2 = 10,000 cycles for 100 elements. Theirs has one loop ("linear") and requires about 100 cycles for 100 elements.

Upvotes: 1

Related Questions