All Questions
Tagged with complexity sorting
7 questions
-4
votes
1
answer
420
views
What is the worst case Time Complexity for only the Divide Portion of the Merge Sort Algorithm?
Please, consider the below merge sort algorithm. Here we start with a divide portion which splits the array into halves and we do recursive operation on each half separately. I have ignored the merge ...
- 1
2
votes
2
answers
4k
views
Can nested loop have linear time complexity
I was going through the traditional quick sort algorithm. I had a look on the partition algorithm in a couple of places and the implementation difference was very subtle. Here are the 2 approaches:
...
- 33
-1
votes
2
answers
312
views
Why in Tournament Sorting do we neglect the number of comparisons to find the Minimum?
Here the professor said that, Tournament sort needs (n-1) + 2(n-1)logn comparisons.
{Where (n-1) for calculating Maximum or say creating Tournament structure
and
2(n-1)logn for other elements to sort}...
- 47
2
votes
4
answers
3k
views
How does the dividing Step in Merge Sort have Constant Time Complexity?
I am highly confuse while calculating time complexity of Merge Sort Algorithm.
Specifically on the Dividing Step.
In the dividing step we have to calculate the mid point of "n" i.e. "q = n/2".
How ...
- 47
-2
votes
2
answers
4k
views
Most efficient way to find top values
Let's say we're given n positive integers in random order. What's the most efficient way to find the m largest elements and what's the complexity?
For example, given 1000 values, find the top 10.
- 19
-3
votes
1
answer
91
views
complexity of an algorithm, sorting 5% out [duplicate]
I have been asked the following question..
An algorithm considers n elements, sorts 5% of n out, considers the remain elements(95%), sorts 5% of the remain elements, and so on until finally one last ...
2
votes
8
answers
20k
views
Merge sort versus quick sort performance
I have implemented merge sort and quick sort using C (GCC 4.4.3 on Ubuntu 10.04 running on a 4 GB RAM laptop with an Intel DUO CPU at 2GHz) and I wanted to compare the performance of the two ...
- 19.8k