What is the time complexity of the code below?
1 2 3 4 5 6 |
|
Assume that arithmetic operations take constant time regardless of the size of the input.
Let be a fixed constant. You are given a set of positive integers less than , and you are tasked to sort it.
Which of the following is the asymptotic running time of the fastest possible algorithm?
Ryan is implementing a merge sort algorithm that he heard about in computers class. However, he wasn't paying attention, and ended up implementing the merge sort in a very unusual way.
The standard merge sort takes a list, and recursively splits it in half, until there is only one element left. It then uses the idea that two sorted lists can be easily merged in time using "two pointer technique" (this step is usually called merge
).
Ryan doesn't know about two pointer technique, however, so he decided to replace merge
with a bubble sort! The bubble sort runs in time.
What is the runtime of this merge sort implementation?