Algorithm Efficiency

 

Algorithm Efficiency

 

Algorithm Efficiency is an area on which the computer science puts a great emphasis because the choice of algorithm would have a great impact on the application’s performance. Sometimes in a more extreme case, the effectiveness of software is solely dependent on the algorithm efficiency. For example, if the algorithm installed on the life supporting system runs too slow, it may even endanger its patients. Also the ramification of efficiency’s impact extends to the commercial value of the software, in that it is directly related to the hardware and the proficiency of a business. In conclusion, a prospective programmer will take the algorithm efficiency into careful consideration upon their selection of algorithm.

 

Order of Magnitude and Big O Notation

 

The algorithm is commonly analyzed and its efficiency is expressed in the Big O notation. When algorithm A requires time proportional to f(N), it can be written order f(N), or denoted as O(f(N)).

 

The Big O notation includes several mathematical properties that help to simply the analysis.

 

  1. In a Big O notation, the low-order terms in an algorithm’s growth-rate can be omitted.
                Example:

O( N3  + 4 * N2 + 3 * N ) can be simplified as O ( N3 )

  1. The multiplicative constant in the high order of an algorithm’s growth-rate function.
                Example:

O( 4* N3  + 4 * N2 + 3 * N ) can be simplified as O ( N3 )

  1. O(f(N)) + O(g(N)) = O(f(N) + g(N))

 

Effective Organization of Algorithm

 

To choose the most suitable algorithm, the programmer must stay in perspective at evaluating efficiency with respect to the situation the algorithm applied for. The programmer has to always keep in mind that the use of a more complex algorithm is only effective if it improves the speed significantly. If the program is merely expected to process a small amount of records, the big O notation will not have a big effect on the efficiency. The choice of algorithm solely depends on the situation and there is not one algorithm that suits all case.

 

For instance, a word processor’s spelling checker conducts intensive retrieving of data, but rarely any insertion and deletion. Since a great emphasis of this operation is put on retrieving the data, an array would be more appropriate. On the other hand, if the application requires frequent insertion and deletion, the pointer-based linked list would be a more suitable solution in this case. These examples demonstrate the basic approach to find the proper algorithm. Although problem can indeed get more complex, the principle remains the same – the best solution is one that satisfies, with maximum efficiency, most important aspects of the program.

 

Analysis of the Non-recursive Algorithm

 

The Big-O notation is derived from a series of calculation which mathematically examines the number of the operations performed by the methods. While the Big-O represents the proportional speed in which the program executes, further analysis can be done to consider a program’s efficiency in terms of its storage requirement. Here we will examine the algorithm listed under the previous heading: linear search, bubble sort, binary search, and selection sort.

 

Usually, a particular algorithm does not remain consistent as the complexity of the problems differs from case to case. Therefore, when analyzing an algorithm, a worst-case analysis is used to evaluate the efficiency worst scenario that can occur. Although the outcome of such analysis can turn out to be quite pessimistic, it has shown that the algorithm will never be slower. The worst case rarely occurs. These following Big-O rating would be drawn from worst-case analysis.

 

Linear Search (Sequential Search)

 

In the worst case of a linear search, the searched item is the last item. So the system needs to perform N amount of comparison at a data structure whose length is N. Since N is the number of operations involved in the worst-case, the Big-O rating would be O(N).

 

Binary Search

 

The binary search searches a sorted array by repeatedly dividing the array in half. The binary search simplifies the problem, then again, until the problem is reduced to only the size of one item that contains the desirable results. The search goes through the following steps:

 

(Suppose that N = 2k)

  1. Inspect the middle item of an array of size N.
  2. Inspect the middle item of an array of size N/2.
  3. Inspect the middle item of an array of size N/22.

 

Every time the algorithm divides the problem into half, an operation is performed. So to solve the problem, k number of comparison and division will be performed. Because N=2k,

 

            k = log2N,

 

Therefore, the Big-O rating for the binary search in its worst case is log2N. The efficiency has proven to be much superior to the linear, for that a data with 1,000,000 items only requires time proportion to about 19, whereas in linear the time required is proportional to a million. However, a sorted array when it is extremely large can be difficult and costly to maintain.

 

 

Selection Sort

 

In general sort, the essence of selection sort involves comparing items, and exchanging items’ positions. The analysis is done with the reference to the selection sort code from Walls and Mirrors (at page 405 ~ 406). The preliminary for loop executes the function SelectionSort N – 1 times. During each execution, the functions IndexOfLargest and Swap are called. In total, these functions are executed for N – 1 times. Inside the function IndexOfLargest, the loop executes for Last times each time. For Last charges from N – 1 down to 1, the loop runs for a total of

            (N – 1) + (N – 2) + … + 1 = N * (N – 1) / 2

times. Since each of these loops perform one comparison, the number of comparisons been done in total is also

 

            N * (N – 1) / 2.

 

The Swap is also performed for N – 1 times. Since each time a swapping is performed, three operations are required. The total number of swapping would be accounted by the following.

 

            3 * (N – 1)

 

To conclude the Big-O, we add the total comparisons and operations together.

 

            N * (N – 1) / 2 + 3 * (N – 1) = N2/2 + 5 * N/2 - 3

 

After applying the rules of Big-O, which eliminates the coefficient and the lower degree terms, the Big-O for selection sort is N2.

 

Bubble Sort

 

Looking upon the bubble sort algorithm, we can notice the presence of the nested loop. Since the double nested loops has both based the condition around the same set of variables. The Big-O notation for this circumstance shown to be O(N2).

 

 

 

Order of Magnitude of Different Types of Algorithm

 

Rate of Growth

Big O Functions

Growth in complexity with growth in number of components

Type of Algorithm

Constant

O(1)

The time requirement is constant.

Array, Perfect Hatch table

Very slowly, hardly any growth

Log2N

The time required increases slowly as the problem size increase

Binary Search

Linear

N

The time is proportional to the component added.

Sequential Search

Nearly linear

N*log2N

Grow a bit more rapidly than linear. It is usually the algorithm that uses the “divide and conquer” technique.

Quick sort

Quadratic

N2

The growth increases two times for every additional component

Insertion sort, bubble sort, selection sort

Cubic

N3

The growth increases three times for every additional component

Triple nested loops

Exponential

2N

The growth increases at an exponential rate, which is too slow to be practical

None.