Sorting Time Complexities

[shamieh]

Don't really need help, already know how to do what I need to do..Was just wondering if anyone knew off the top of their head the average case time complexity of



Linear Search

Binary Search

Selection Sort



To find these would I just divide by 2?



I only have found two so far.



Bubble sort = n(n+1) / 2

and

Insertion sort = n(n-1)/2 (I think)

[Cody0023]

I think you are trying to refer to Big O notation.

I know linear search is O(n).

[shamieh]

No, big O would be like On The Order of, I am looking for the Average Case Time Complexities, big O, for example, would be something like this

For Bubble Sort

n(n+1) /2 = n^2 + n / 2 = O(n^2) or "Quadratic"

But see I am trying to find the Average Case Time Complexities.

[Smac89]

It the list is sorted, binary search on average will always take O(lgN) because the best and worst time complexity is O(lgN).

For linear time it should be O(N/2) on average

For selection sort, best case is still O(N²) because no matter if the set of items is already sorted, selection sort still needs to iterate through the entire list to verify this. So the average time complexity is still O(N²).

You are basicallly looking for big Theta. Google it

[shamieh]

Smac89, so would the average time complexity of Binary Search then be Logn / 2 ?

Also, can you verify that my insertion sort formula is correct?

For Selection sort I have obtained this:

Selection Sort: [ (n(n+1)) / 2 ] - 1

Is this correct?

In addition, as easy as you make it sound, it's not that simple. I tried googling for hours, but I keep getting the BEST and WORST case time complexities, and what I need is the AVERAGE time complexities of these. Don't believe me? Try to Google it yourself lol. There are seriously no results giving me what I need.

Thank you for your time, hopefully you can verify if what I've submitted is correct.

I'm also wondering if I can just take the best and worst TC's and add them up and then divide by 2 to get the average case? Would that be plausible?

[Smac89]

I mentioned in my last post that what you want to find is big theta notation. This is different from notations such as Big O, Big Omega, etc. Where Big O measures the upper bound cost, and Big Omega measures lower bound cost; Big theta will lie somewhere between Big O and Big Omega

http://lmgtfy.com/?q=big+theta+notation
http://stackoverflow.com/a/12338937/2089675

The stackoverflow link will explains it in more detail.

You average case for selection sort looks about correct because in the worst case and best case, the algorithm will do:
N - 1 + N - 2 + N - 3 + ... + N - (N - 1) comparisons to determine if the list is sorted
= 1 + 2 + 3 + 4 + ... + N - 1
= (N - 1)(N) * 1/2
= ¹/₂ * N² - N

I will try to upload a lecture video (or 2) that I found that can explain this to you

http://osric.com/chris/accidental-developer/2012/04/robert-sedgewick-algorithms-for-the-masses/

These videos are by Robert Sedgewick, provided in his free online course at coursera.org: https://class.coursera.org/algs4partI-004
I suggest signing up for future offerings of this class

http://goo.gl/cKLmrF
http://goo.gl/MzwqR7
http://goo.gl/x6m15D

[shamieh]

Thank you.