CODEWITHSUNDEEP
bubble-sort
phone1021
phone1021

Reputation: 29

Bubble Sort in O(n)?

I know traditionally bubble sort is n^2 time complexity, but I wrote my own implementation of it and to me it looks O(n). I don't see how it can be n^2 because I don't have any nested loops. Even when I call it recursively in a loop, I break the loop right after the recursion.

def bubblesort(x):
    index = 0
    while index <= len(x) - 2:
        if x[index + 1] < x[index]:
            temp = x[index + 1]
            x[index + 1] = x[index]
            x[index] = temp
        else:
            index += 1
    print(index)
    index = 0
    while index <= len(x) - 2:
        if x[index + 1] < x[index]:
            bubblesort(x)
            break
        else:
            index += 1

Upvotes: 0

Views: 110

Answers (1)

Joshua
Joshua

Reputation: 43280

If I unwrap the tail recursion it's clearly a nested loop for O(N^2)

def bubblesort(x):
    do
        index = 0
        while index <= len(x) - 2:
            if x[index + 1] < x[index]:
                temp = x[index + 1]
                x[index + 1] = x[index]
                x[index] = temp
            else:
                index += 1
        print(index)
        index = 0
        while index <= len(x) - 2 and x[index + 1] >= x[index]:
            index += 1
    while index <= len(x) - 2 and x[index + 1] < x[index]

Upvotes: 1

Related Questions