Google Answers Logo
View Question
Q: Data Structure and Algorithm in Java ( Answered,   1 Comment )
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
 while (P is not empty)
Subject: Re: Data Structure and Algorithm in Java
Answered By: haversian-ga 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 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.
Subject: Re: Data Structure and Algorithm in Java
From: coble-ga 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

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy