

Subject:
Data Structure and Algorithm in Java
Category: Computers > Algorithms Asked by: math01ga List Price: $5.00 
Posted:
28 May 2003 06:13 PDT
Expires: 27 Jun 2003 06:13 PDT Question ID: 209764 
The following algorihm is used to create a sorted priority queue. Estimate the runtime using big O notation. Algorithm Sort(L, P): Input: A sequence L (linked list) of n elements (student records). Priority Queue P. Output: Sorted sequence L in increasing order of scores. while (L != null) do P.insertItem(L.removeFromHead()); while (P is not empty) L.insertAtTail(P.removeMin()); 

Subject:
Re: Data Structure and Algorithm in Java
Answered By: haversianga on 28 May 2003 18:28 PDT 
The first while loop is O(n) (it executes n times), thus its runtime is proportional to n, the length of your linked list. The contents of the loop are O(1) for the removeFromHead, a constanttime operation in a linkedlist (assuming a head pointer). If your priority queue is implemented in a way that an insert occurs in O(1) (constant) time, the entire loop is O(n). If the insert executes in O(n) time, the loop as a whole is O(n*n) = O(n^2). The second while loop also executes n times, and its contents are a constanttime insert operation and a P.removeMin. If the P.insert in the first loop completes in constant time, the removeMin will require a search, which will be O(n). If P.insert takes O(n) time, the removeMin will probably take O(1) time. Thus, one of the whiles will complete in O(n), and one will complete in O(n^2) time, for a total of O(n^2) for the entire algorithm. It may be possible to code a P.insert and P.remove in such a way that both take O(log n) time, perhaps by using a tree of one form or another; the entire algorithm would then take 2 * O(n log n), or O(n log n) time. If you can provide (pseudo)code for the insert and remove methods, I can tell you which of the above possibilies is correct. 

Subject:
Re: Data Structure and Algorithm in Java
From: coblega on 28 May 2003 09:02 PDT 
I'm assuming that since P is a priority queue, P.insertItem(L.removeFromHead()) will put the first element of L into its proper place in P. This while loop is order O^2, because in the worst case scenario, you will have to traverse the entire priority queue. In big O notation [n * 1] + [(n  1) * 2] + [(n  2) * 3 ] + ... + [ 1 * n ] is O^2. Answer: O^2 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 