CODEWITHSUNDEEP
pythonbig-otime-complexity
user3096874
user3096874

Reputation: 3

Time Complexity of loops

Here is my code. I have to find the time complexity if this code. I gave two answers for this code. one is O(n log(n)) and O(n). But both are wrong. [I gave these answer based on the loop structure. I have seen some codes with for loop within the while loop. and those types of codes have the time complexity of O(n log(n)).] Can any one suggest me the right answer ?

def sort1(lst):
    swapFlag = True
    iteration = 0
    while swapFlag:
        swapFlag = False
        for i in range(len(lst)-1):
            if lst[i] > lst[i+1]:
                temp = lst[i+1]
                lst[i+1] = lst[i]
                lst[i] = temp
                swapFlag = True

        L = lst[:]  # the next 3 questions below refer to this line
        iteration += 1
    return lst

Upvotes: 0

Views: 669

Answers (1)

aga
aga

Reputation: 29416

It looks like some kind of bubble-sort, which has time complexity of O(n^2).
Here on every iteration of inner for loop you're shifting the maximal element to the end of the list, making n-1 comparisons. There're n elements in the list, and the inner for loop will be executed once per each element, giving O(n^2).

Upvotes: 1

Related Questions