View Question
Q: Data Structure and Algorithm in Java ( Answered,   1 Comment )
 Question
 Subject: Data Structure and Algorithm in Java Category: Computers > Algorithms Asked by: math01-ga 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());```
 ```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 constant-time operation in a linked-list (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 constant-time 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.```
 ```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```