How to describe an algorithm?

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.
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

Christopher KileConnect With a Mentor Commented:
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.


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.
secondcup, i wonder why you find it necessary to set us school work? We know Java here ...
do you mean  o(n log log n) or O(n + max miles)?
The new generation of project management tools

With’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

secondcupAuthor Commented:
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..
So you'd better come up with some code as per the site conventions, and try to stop wasting our time.
Jose ParrotGraphics ExpertCommented:
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 ParrotGraphics ExpertCommented:
Jose ParrotConnect With a Mentor Graphics ExpertCommented:

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.

Christopher KileCommented:

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

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).
Jose ParrotGraphics ExpertCommented:
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

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

Algorithm 1 - Constructing the BST
   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
   total = log N
   for i =1 to total
      B[i] = A[i]

Open in new window

Jose ParrotGraphics ExpertCommented:
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).


All Courses

From novice to tech pro — start learning today.