Solved

How to describe an algorithm?

Posted on 2008-06-16
14
1,985 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Optimize your web performance

What's in the eBook?
- Full list of reasons for poor performance
- Ultimate measures to speed things up
- Primary web monitoring types
- KPIs you should be monitoring in order to increase your ROI

 
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:Jose Parrot
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
 
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:Jose Parrot
ID: 21819511
Not exactly ONE OPERATION, but a CONSTANT NUMBER OF OPERATIONS instead.
0
 
LVL 18

Assisted Solution

by:Jose Parrot
Jose Parrot 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:Jose Parrot
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:Jose Parrot
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

Get MongoDB database support online, now!

At Percona’s web store you can order your MongoDB database support needs in minutes. No hassles, no fuss, just pick and click. Pay online with a credit card. Handle your MongoDB database support now!

Question has a verified solution.

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

One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
Suggested Courses

617 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