Classify each of the following algorithms as linear, polynomial (but slower than
ID: 3766274 • Letter: C
Question
Classify each of the following algorithms as linear, polynomial (but slower than linear), or exponential. Consider the algorithmic growth relative to N: as N grows, how does the algorithm's time requirements grow?
1. Surveying N people in a room to find out the political affiliation of each.
2. Recording each score for a round-robin tournament of N teams (in a round-robin tournament, each team must play against every other team)
3. Counting how many credit cards (in a collection of N credit cards) have a negative balance.
Explanation / Answer
1) An algorithm is said to be a linear time algorithm, if its time complexity is O(n).
The algorithm used to survey N people in a room to find out the political affiliation of each is a linear algorithm, because each person is enquired one by one about political affiliation, thus it takes N steps only.
Therefore the algorithm running time increases in O(n) as N grows.
2) An algorithm is said to be a polynomial time, if the number of steps required to accomplish the task by the algorithm with a given input of size n is O (nk) for some nonnegative integer k.
That is , the time requirement increases in O(n2) as the N increases and the algorithm is a polynomial algorithm.
3) An algorithm is said to be exponential time, if its time complexity is O(2nk) for some constant k.
That is, the time required find credit cards with negative balance increases in O(2N) as N increases.