Understanding time complexity in two nested while loops

Question

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!!

Amit · Accepted Answer · 2015-07-23 22:37:03Z

1

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.

answered Jul 23, 2015 at 22:37

Amit

46.5k9 gold badges84 silver badges114 bronze badges

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

Collectives™ on Stack Overflow

Understanding time complexity in two nested while loops

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related