This is a homework I'm doing, but I couldn't find an answer, hopefully you guys can shine some light on this.
The problem is this:
You have two unknown sorting algorithms, one is Bubble Sort, the other Insertion Sort.
Identify which is which given that you can only differentiate them via differences in asymptotic time for different data sets. (Meaning no run time cross comparison between the two sorts, as our professor may add constant time costs making Insertion Sort slower).
Edit: To clarify, we can specify any array of length n, with a particular sequence if you wish, to see the time it took to sort.
However, you may not compare times between the two sorts. E.g. This sort is faster, therefore this is Insertion Sort.
My findings:
Insertion Sort | Bubble Sort
Best case: O(n) | O(n)
Worst case: O(n^2) | O(n^2)
Average case: O(n^2) | O(n^2)
Stable: Yes | Yes
In-place: Yes | Yes
Nearly Sorted: O(n) | O(n)
Reversed: O(n^2) | O(n^2)
Few Unique: closer to O(n) | closer to O(n^2) // not sure
Given how similar the two sorts are, it's really hard to distinct them...