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** ?

For the worst case time complexity of Bubble Sort I obtained:

For example if I have the list:

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

As well as the following information:

For

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 N^{2}

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

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

Topic archived. No new replies allowed.