CODEWITHSUNDEEP
data-structurestime-complexity
deep
deep

Reputation: 716

Understanding time complexity in two nested while loops

I came across this code. It scans through the array elements only once. But I am confused regarding having two nested while loops increase the complexity to O(n^2). The code is as follows:

def summaryRanges(nums):
    x, size = 0, len(nums)
    ans = []
    while x < size:
        c, r = x, str(nums[x])
        while x + 1 < size and nums[x + 1] - nums[x] == 1:
            x += 1
        if x > c:
            r += "->" + str(nums[x])
        ans.append(r)
        x += 1
    return ans

I am learning algorithms so please correct me if I am going wrong somewhere. Thank you!!

Upvotes: 0

Views: 74

Answers (1)

Amit
Amit

Reputation: 46341

Your question isn't 100% clear, but if you meant why is this NOT O(N^2) while having nesting loops then:

Although there are nesting loops, they operate on the same space using the same variable to advance the iteration. since the inner loop doesn't backtrack, and whenever it moves ahead it also pushes the outer loop ahead (at the exact same distance), the iteration won't grow larger then M if N grows by M (If N1 = N0 + M). O(N^2) means that as N grows, the iteration grows exponentially.

Upvotes: 1

Related Questions