Solved

How to describe an algorithm?

Posted on 2008-06-16
14
1,960 Views
Last Modified: 2010-05-18
An airline wants to give a first class upgrade coupon to their top (log n) frequent flyers, based on the number of miles accumulated, where n is the total number of the airlines' frequent flyers. The algorithm they currently use, which runs in O(nlogn) time, sorts the flyers by the number of miles flown and then scans the sorted list to pick the top log n flyers. Describe an algorithm that identifies the top log n flyers in O(n) time.
0
Comment
Question by:secondcup
  • 5
  • 2
  • 2
  • +3
14 Comments
 
LVL 86

Expert Comment

by:CEHJ
ID: 21795811
secondcup, i wonder why you find it necessary to set us school work? We know Java here ...
0
 
LVL 84

Expert Comment

by:ozo
ID: 21796145
do you mean  o(n log log n) or O(n + max miles)?
0
 

Author Comment

by:secondcup
ID: 21796739
Basically, I have to change the current algorithm which runs in O(n log n) time to another
algorithm running in O(n) time to choose the top log n flyers..
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 21798117
So you'd better come up with some code as per the site conventions, and try to stop wasting our time.
0
 
LVL 18

Expert Comment

by:JoseParrot
ID: 21798713
Nothing against homework, just we cannot solve it to you, but we can give you a guidance. Assuming that advisoring is all you want, then ...

First you need to sort frequent flyers by milleage account, from highest to lowest. This is typically O(n log n)  if using quicksort or mergesort. Faster algorithms, are more complicated (they use mid of 5, mid of 3) and are more effective to large numbers. So I'm assuming a mistake here, that is, the sorting is actualy O(n log n).

About chosing the top flyers, it is clearly O(n). A simple for count from 1 to log n is enough, starting from highest milleage customer.

Jose
0
 
LVL 84

Expert Comment

by:ozo
ID: 21798737
0
Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 23

Accepted Solution

by:
Christopher Kile earned 250 total points
ID: 21813711
second cup,

O(n) implies you get ONE PASS through the data and ONE OPERATION per data item.  You're making a list of log n frequent flyers of all the n frequent flyers.  How would you do this if it was a set of index cards, and each card had the name and mileage a frequent flyer?  I guarantee that if you buy some index cards, write a name and an amount on each card, then start trying this task by hand, the answer will come to you probably within an hour.

Moderators,

I am not doing second cup's homework, but I hope my suggestion will lead him to find a solution for himself without giving more help than a teaching assistant might.  Please let me know if this still violates EE guidelines and rules.
0
 
LVL 18

Expert Comment

by:JoseParrot
ID: 21819511
Not exactly ONE OPERATION, but a CONSTANT NUMBER OF OPERATIONS instead.
0
 
LVL 18

Assisted Solution

by:JoseParrot
JoseParrot earned 250 total points
ID: 21819639
secondcup,

As the problem has two steps solving (sorting and picking), and as the sorting is O(n log n) and the picking is O(n), total complexity is O(n log n).

If you must solve it in linear time, say O(n) then the sorting algorithm should be O(n), then using a mid-of-five or  mid-of-seven pivoting. If, so, my previous assumption was wrong, say, there are no mistake...

Abot mid-of-3 or -5 algorithms, the median calculation itself spends an  additional time, so, despite the algorithm to be O(n), the number of operations can be quite high, thus not resulting in less execution time than quicksort algorithm, when n is not so big. For large n values, this algorithm is efficient.

The link provided by ozo describes well an algorithm with such approach, and theoreticaly sorts in O(n) execution time.

As soon you have the flyers sorted, from higher to lower, just pick the F first in the list, being F= n log n.

Now, both steps are O(n), thus resulting in O(n) for the problem at all.

Jose
0
 
LVL 23

Expert Comment

by:Christopher Kile
ID: 21822435
JoseParrot:

Yes, more or less :)  O(an + b) = O(n).

secondcup,
If it's legitimate question and not homework, here's the answer:

insert everything into a binary tree with an additional property per node, total nodes in this subtree including the root node (it is simple to update this value at each node during insertion).  Once the tree is built, traverse down the leftmost branch until you reach a node where the total subnodes of this node = log n.  The parent and right sibling of this node are smaller than any of the nodes in this subtree.  No balancing is required.

Insertion into the tree is O(n).  Searching for the correct subtree is O(log n) and is performed once for the entire set of n, thus it is constant over the same n used by the insertion.  Combined, the insertion and search are O(n + log n) = O(n).
0
 
LVL 18

Expert Comment

by:JoseParrot
ID: 21892676
Searching can be O(log n) in a BST, but firstly the BST must be constructed.
To construct a BST we have the algorithm 1 below.
Algorithm 1 analysis
Insertion in BST is O(n) worst case if nodes are in a single chain, or is O(log n) if the tree is balanced. As there are n flyers, the insertion is made n times, so
Algorithm 1 is O(n log n) best case to O(n²) worst case.
The total complexity of such operation (construction + searching) will be O(n + n log n) = O(n log n) or, in the worst case, O(n + n²) = O(n²).
BST and B-Trees are good for database on random access, where we do searching several times and each element is inserted once.

In the present problem, the whole operation must be accomplished in O(n), so
both Sorting and Picking must be O(n).

Sorting in O(n) is quite complicated (actually a three steps algorithm) and is described  by Dr. Karl-Dietrich Neubert in the Dr. Dobb's Journal February 1998.
Complete article at http://www.neubert.net/Flapaper/9802n.htm

Picking is clearly O(n), as in the Algorithm 2 below.

Jose
Algorithm 1 - Constructing the BST

ConstructBST

{

   foreach flyer                 // n flyers

   {

      insert flyer in the BST    // O(log n) or O(n) worst case

   }

}

---------------------------------------------------------

Algorithm 2 - Picking

input: array A[1..n] with elements sorted in non-crescent oreder

       N, the number of elements in the array

output: array B[1..log n] with (log n) higher flyers

Picking

{

   total = log N

   for i =1 to total

   {

      B[i] = A[i]

   }

}

Open in new window

0
 
LVL 18

Expert Comment

by:JoseParrot
ID: 21898874
Hi, secondcup,
A little clarification: any loop executing from 1 to n is O(n), say it executes in linear time. As we use to consider constant time as O(1) and linear time O(n), I have pointed Algorithm 2 above as O(n). But in the specific case of the problem as posted, Algorithm 2 executes in O(log n). BTW, Theta(log n).

Anyway, the total time remains O(n):
Sorting --> O(n)
Picking --> O(log n)
O(n) + O(log n) = O(n + log n) = O(n).

Jose

0

Featured Post

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

705 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

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now