### WORST Case Time Complexity

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 ?
Last edited on
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 N2

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
Topic archived. No new replies allowed.