0
$\begingroup$

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...

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ I find the problem statement unclear. Exactly what is allowed? What does the problem statement mean by "asymptotic time for different data sets"? Does it mean you are allowed to provide an input to the sorting algorithm, and then observe how long the algorithm takes? But asymptotic running time is not about a single data set, but rather an infinite sequence of data sets. So exactly what form of differentiation is allowed? Can you edit to clarify? If you're not sure, then it sounds like your next step is to ask your instructor what he/she intended by the question. $\endgroup$ – D.W.♦ Jan 30 '16 at 5:30
  • $\begingroup$ @D.W. We are allowed to compare data sets run time for each sort, meaning we can compare run times for n = 100 vs n = 1000000 to see if the sort did it in O(n) or O(n^2) for let's say, a reversed sorted data set. $\endgroup$ – Kai Jan 30 '16 at 5:34
  • 1
    $\begingroup$ I stand by my prior comment. Looking at the running time for finite values of n does not tell you what the asymptotic running time is. You can't tell whether a program is $O(n)$ or $O(n^2)$ by looking at running time for a few finite values of $n$. Asymptotic running time, by definition, refers to the behavior of the running time for a set of infinitely many input sizes. It sounds like the problem is not well-posed. Perhaps we can try to guess what might have been intended, but if we take the wording literally, it does not seem well-defined. $\endgroup$ – D.W.♦ Jan 30 '16 at 5:50
  • $\begingroup$ Anyway, even with your comment, it's still not exactly clear what we are allowed to do. Are we allowed to specify a specific input and see the running time on that input? To specify a value of $n$ and see the maximum running time over all arrays of length $n$? To specify an infinite sequence of inputs and learn the asymptotic running time for that sequence of inputs? Something else? It's not clear. Please edit the question to clarify exactly what we are allowed to do and exactly what value we learn in response. $\endgroup$ – D.W.♦ Jan 30 '16 at 5:52
  • 1
    $\begingroup$ The problem is ill-posed. You can not hope to get asymptotics from a finite sample of running times. $\endgroup$ – Raphael♦ Jan 30 '16 at 13:07
3
$\begingroup$

Unfortunately, your problem statement is contradictory, so the problem cannot be solved in its current form. Your question states that we can obtain the running time for finite values of $n$. However, it also states that we only learn the asymptotic running time. This is self-contradictory, because it is not possible to infer the asymptotic running time based on any finite number of measurements.

If I had to speculate, I'd guess that maybe what the instructor actually wants you to do is find an infinite sequence of inputs $a_1,a_2,a_3,\dots$ such that: (1) $a_i$ is an array of length $i$; (2) the asymptotic running time of Insertion Sort on these inputs differs by more than a constant factor from the asymptotic running time of Bubble Sort on these inputs. If that's correct, your next step should be to investigate various ways you might construct such a sequence. I emphasize that this is only speculation, and not something that can be definitively derived from the problem statement as provided.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for continually answering my queries. Perhaps I misunderstood the question given and need to investigate more thoroughly. $\endgroup$ – Kai Jan 30 '16 at 7:48
  • $\begingroup$ I found out a difference! InsertionSort will sort the sequence [1,3,3,3,3,3,...,3,2] in O(n) time while BubbleSort will only do it in O(n^2) time. $\endgroup$ – Kai Jan 31 '16 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.