WORST Case Time Complexity

[shamieh]

I am finding the Worst Case time complexity for Bubble Sort, Selection Sort, Insertion Sort, Linear Search, & Binary Search..

For the worst case time complexity of Bubble Sort I obtained: (n(n-1)) / 2.

For example if I have the list: 6 5

After using Bubble Sort to sort the list I would obtain: 5 6

As well as the following information:

Theoretical Sort Statistics: 1 element comparisons, 2 element movements Actual Sort Statistics: 1 element comparisons, 1 movements

For Insertion Sort, would I obtain the same result for the worst case time complexity as: (n(n-1))/2 ?

[Smac89]

http://www.cplusplus.com/forum/beginner/126196/

Yes insertion sort will take about the same worst case example being when the list is in descending order

Selection sort is always N²

Linear search is linear O(N)

Binary search depends on if the tree is balanced or not. Unbalanced binary search tree can turn into a linked list in the worst case if the elements added are in descending order so O(N) time complexity. But a balanced binary search tree is always OlgN