complexity of algo

Posted on 2003-10-31
Last Modified: 2007-12-19
I got some questions about complexity of shell sort and heap sort
I know worse case, average case of heap sort id O(n log n)
um...i'm just woundering whether the best case is also nlogn, and what if he complexity of heap sort for a sorted file..( i think those two stillO(nlogn), cos bulild the heap: O(n) + sort the heap still(log n) no matter the file is sorted or not)
but I'm not sure....

why the best case comlexity of shell sort is O(nlogn) not O(n^1.25)?

Question by:redsar
  • 4
  • 3
LVL 11

Expert Comment

ID: 9663452
What is the best case of a sort? This is typically not a relevant question because the best case typically can only happen for an already sorted input and, as n goes up, the probablilty of that input happening is smaller and smaller (arbitrarily close to 0).

For heapsort: if the file is reverse sorted (reversed from the order you want to end up with) then the array already contains an appropriate heap. Thus insertion into the heap is O(n). The extract operation (extract_min or extract_max, depending on order of heap) is stil going to promot the last element to the root of the heap and push it back down to where it belongs. Thus it is an O(lg n) operation performed for each extraction or O(n lg n) for all of them. O(n) + O(n lg n) = O(n lg n).

But wait, is this the very best case? What if the array is monotonic (contains only one value)? Then the heap is already in place as before (O(n) to realize this) _and_ promoting the farthest leaf to the root does not break the heap property so there is nothing to push down in the heap; extract becomes  O(1) and is done n times: O(n) for all of the extraction operations: O(n) + O(n) = O(n). The best case is linear in array size. It requires a monotonic array to sort so it is unlikely to be of any real use but this is the best case.

I don't have my algorithm text handy so I can't perform the same analysis for shell sort but if I were to guess where the "best" performance would be I would try a monotonic array.

Hope this helps, -bcl

Author Comment

ID: 9665084

thank you very much.
what about the best case comlexity of shell sort is O(nlogn) not O(n^1.25)?

i know it is based on the sequence, any sequence gives O(nlogn)?

and I'm just woundering the space complexity of quick sort , is that O(1)( in place), O(longN) or O(N)?
why we need the stack ?
LVL 11

Expert Comment

ID: 9665650
This sounds a lot like homework. It is the policy of EE not to do homework. I can offer some guidance.

So, you know that any sequence requires n lg n time to process with shell short. That means a monotonic array, a sorted array, a reverse sorted array or a completely random array will take that amount of time. If you believe that any sequence takes that amount of time then you are done showing that the best time is O(n lg n). Why do you believe that any sequence takes that long to sort? Explain it to me using the algorithm and I can help you with any speciific problems you have.

As to space complexity of quicksort and the use of a stack: Quicksort sorts the array in place (that is there is no additional array allocation required as there is in mergesort, for example). That is not the whole answer, though. Bubblesort uses O(1) additional space (we are talking about space BEYOND the original array) because you only need a couple of loop control variables and a temporary storage location for the swap; in particular, notice that bubblesort doesn't need recursion or an explicit stack, just some variables. Now think about what gets stored on quicksort's stack and why there needs to be a stack and not just a variable or two.

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!


Author Comment

ID: 9666242
i guess it is a misunderstanding because of my english.

the question about shell sort is....
cos I think the best case time complexity should be O(n^7/6) by Sedgewick,

but the answer is O(nlogn)
i'm just woundering why this is O(NlogN)

um...about the quick sort..
I have read through some pages on Sedgewick...
the subfiles in stored in the stack , when we need that, pop them off, and partioning and then push them back to the the average space complexity is o(logn) and the worst case is
O(N) when the file is sorted...Is that right?
LVL 11

Expert Comment

ID: 9666349
Do you have to push copies of portions of the array on the stack for quicksort? Or can you get by with just the endpoints of a range in the array? If you push the endpoints of a range you need a constant amount of space each time you push on the array. Thus the total amount of space used is proportional to the maximum depth of the stack. What is that maximum depth in the best case? What is it in the worst case? The average case?

Well, the worst case is simple: If we partition off one item at a time then there will be n levels pushed on the stack at its deepest. Thus the storage, worst case, is O(n). More interesting is the average case. How deep does the stack get?

Note: Shellsort is not one I tend to teach so my knowledge of analysis of it is limited. I was just reading which works on lower bounds and goes beyond Knuth's work but I don't really have a good description of the proof (I can follow the paper but would not have gone there myself).


Author Comment

ID: 9666482
Thanks a lot....i think the main problem is I don't know how to calculate the space complexity and time complexity....of course, some questions are very easy, like insertion sort and seletion sort, but for the difficult analysis like quick sort and merge sort...i don't know how to deal with..
anyway thanks a lot..
LVL 11

Accepted Solution

bcladd earned 40 total points
ID: 9666615
The first step to calculating complexity is figuring out what is executed/allocated most often. Then count how many times that happens.

For quicksort: The key is the recursion. Assuming a perfect pivot (and a power of 2 size of the array), the amount of time it takes to sort a given size array, T(n), is:
    T(n) = T(n/2) + T(n/2) + n

It took n operations to partition the array and it will take however long it takes to sort half of the array TWICE (each half) to finish the sort.
We also know that an array of size 1 is already sorted. This gives you a non-homogeneous recurrance equation. You solve the equation (by converting to a homogeneous equation) and you find that this "perfect pivot" sort has a closed form that is O(n lg n).

Alternatively, think about how many recursive calls will be needed for sorting a size N array. Assuming perfect partition, we need a depth of lg n recursive calls (n, n/2, n/4, n/8, n/16, ..., 2, 1; there are lg n numbers in this sequence and the sequence represents the size of the section of the array being sorted at each recursive call).  If you think about ALL of the recursive calls, the calling diagram is a full binary tree (rooted at the call with size n which has two children, the call to sort the left half of the array (size n/2) and the call to sort the right half of the array (size n/2) and so on.

Does that function call diagram make sense? Total complexity is the total of work done in every node. Since the work is proportional to the size of the section of the array being sorted, each level in the full binary tree contributes O(n) work (each level processes the whole array, one piece per node). Thus the total work is proportional to the height of the full binary tree times n. But there are lg n levels in this binary tree so the total complexity of the sort is O(n lg n).

Hope this helps. Getting a feel for complexity is a challenge (learning how to find and solve recurrance equations can be very helpful if you plan on doing a lot of this).


Featured Post

Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
In this post we will learn different types of Android Layout and some basics of an Android App.
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

685 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question