Solved

# How to describe an algorithm?

Posted on 2008-06-16
1,976 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
Question by:secondcup
• 5
• 2
• 2
• +3
14 Comments

LVL 86

Expert Comment

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

LVL 84

Expert Comment

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

Author Comment

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

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

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

ID: 21798737
0

LVL 23

Accepted Solution

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

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

LVL 18

Assisted Solution

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

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

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

LVL 18

Expert Comment

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

Question has a verified solution.

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

### Suggested Solutions

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â€¦
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â€¦
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â€¦
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 â€¦

#### 740 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.