CODEWITHSUNDEEP
complexity-theorybubble-sort
Kami H
Kami H

Reputation: 31

Bubble sort complexity O(n)

We have the series of numbers.We can see that this series is almost sorted. Since this series is almost sorted does it mean that the complexity is O(n)?

Series

Upvotes: 0

Views: 114

Answers (3)

httpNick
httpNick

Reputation: 2624

This is very vague, but O() notation talks about worst-case runtime. So whatever input is handed to bubble-sort (for instance) can take at most n^2 number of operations to sort. Specific examples may take anywhere from the least amount of operations possible to the most operations possible (with bubble sort that is O(n^2)).

Upvotes: 0

bozzmob
bozzmob

Reputation: 12574

Yes. This example can be considered as O(n).,

There are cases when O(n) and even less than that is possible.

Examples-

Already sorted array (1 2 3 4 5 6)

An array in which only the alternate values are exchanged (2 1 4 3 6 5)

etc.

Keeping these best cases or exceptional cases aside, the complexity of Bubble sort for a given random unsorted array is O(N^2).

Upvotes: 0

Heath Hunnicutt
Heath Hunnicutt

Reputation: 19457

No. There are so many reasons it's hard to know where to start. First, O() notation is not defined for specific input examples. The complexity of an algorithm is defined for any possible input.

Aside from that, even an almost sorted list can require O(N^2) time to sort. Simply take a sorted list, swap the first and last elements, and pass that to Bubble Sort. That seems like it would meet the definition of almost sorted, but Bubble Sort will take N^2 operations to put the list in total order.

Upvotes: 1

Related Questions