Are you thinking about creating an Amazon Web Services account for your business? Not sure where to start? In this course you’ll get an overview of the history of AWS and take a tour of their user interface.

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.

algorithm running in O(n) time to choose the top log n flyers..

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

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

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).

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]
}
}
```

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

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

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.