Shweta Joshi: Efficiency Of Algorithms

The design and implementation of algorithms have great influence on their efficiency.
Every algorithm, when implemented must use some of the system resources to complete its task. The resources most relevant to the efficiency are the use of the central processor unit (CPU) time and internal memory (RAM).
In the past, high cost of the computer resources was the driving force behind the desire to design algorithms that are economical in the use of CPU time and memory.

1)Removing Redundant Computations Outside Loops

Most of the inefficiencies that creep into the implementation of algorithms are due to redundant computations or unnecessary storage. The effect of redundant computation is serious when it is embedded within a loop, which must be executed many a times.
The most common mistake when using loops is to repeatedly recalculate the part of an expression that remains constant throughout the execution phase of the entire loop. Let us take an example:

2)Referencing of Array elements:

Generally, arrays are processed by iterative constructs. If care is not exercised , while programming, redundant computations can creep into array processing.
Consider, as an example, the following two versions of an algorithm in C, to find the maximum number and its position in an array of numbers:

Indexing of any kind, whether it be of simple data elements or of structured elements requires more time. Thus it can be said that the second version of the implementation is preferable because the condition test (that is, a[i] > max) which is the dominant operation is much more efficient to perform than the corresponding test in the version I of the program.
By using the variable max, only one array reference is being made each time, whereas when using the variable p as index, two array references are required.
References to array elements require address arithmetic to arrive at the correct element and this requires time. Thus more time is spent in locating the specific value for comparison.
Secondly, the second version of the program is better documented and the purpose of the code is much more explicit to the reader. This is because; by adding the variable called max we are providing a clue to the reader of the program about its operation.

3) Inefficiency due to late termination:

Another possibility of inefficiency creeping into the implementation of an algorithm is,
When considerably more tests are carried out, than are required to solve the problem at hand. Example: Suppose we have to search an alphabetically ordered list of names for a particular name using linear search.
An inefficient implementation for this case would be one where all names were examined even if a node in the list was reached where it could be definitely said that the name cannot occur later in the list.
For example, suppose we are searching for Ketan, then, as soon as we reach a name that is alphabetically later than Ketan example, Lalit, we should not proceed further.

Shweta Joshi