Efficient Algorithm Writing – Tricks and Examples

Efficient algorithm writing concerns the effectiveness of the overall system. Every real-life algorithm iterates at least once. Iteration may be explicit (due to the looping construct) or it may be implicit (due to recursion). Loops are the major contributor to the efficiency analysis of the algorithm. Sometimes the code within the loop executes thousands of times or even billions of times. A small gain in proper algorithm design greatly reduces the running time.

Effectively using loops

It is just as important to write efficient algorithms as it is to have high-level hardware. The carelessly written algorithm often runs one time more or less than intended. The following three points should be considered while writing a looping construct:

Initialization

Choose the loop counter such that it can address the smallest possible instance of the problem. Consider the problem of summing the first n integers. The smallest possible instance is to add a zero number. In that case, the minimum value of the sum variable and the loop counter i will be zero.

i = 0
s = 0

Find iterative construct

Find the problem with the next smallest instance. A careful inspection of the loop and logic tells us that in each iteration variable i needs to be incremented and A[i] should be added to the partially computed sum.

i = i + 1
sum = sum + A[i]

The complete code segment would be :

i ← 0
sum ← 0
while i < n do
  i ← i + 1
  sum ← sum + a[i]	// Assume that array index starts from 1.
end

Termination

A number of iterations may be known in advance or it may depend on certain conditions to be satisfied. To find
5! loop should be iterated 5 times

The loop count is known in advance:

for (i = 1; i <= 5; i++)
{
	. . . 
}

The loop count is not predefined:

Sometimes loop may be forced to terminate from in-between

for (i = 0; i < n; i++)
{
  if A[i] == x
    break;
}

How to write an efficient algorithm?

Remove redundant operations:

The computational cost of an algorithm is defined by its efficiency. People used to frequently write unneeded code within the loop. Redundant code that is repeated within loops has a negative impact on execution time.

The algorithm’s efficiency can be increased by carefully designing it. Consider the code segment below for determining pixel coordinates along the ellipse boundary:

Algorithm DRAW_ELLIPSE(a, b)

for x ← 0 to a do
  y ← (b/a)*sqrt(a*a – x*x)
  PlotPixel(x, round(y))
end

By relocating the constant computation outside the loop, a substantially better version of the above algorithm can be developed. The optimized ellipse algorithm is illustrated below.

Algorithm EFFICIENT_DRAW_ELLIPSE(a, b)

t ← b/a;
m ← a * a;
for x ← 0 to a do
  y ← t*sqrt(m – x*x)
  PlotPixel(x, round(y))
end

Constant division b/a and constant multiplication a*a are moved outside of the loop, and hence we reduce n multiplications and n divisions.

Referencing Array

One memory access corresponds to a reference to one array element. If the array is large, this may result in a significant number of memory accesses, slowing down the process. The algorithm’s efficient design can save a large amount of memory access.

Arrays are typically used to retain a huge amount of data and are accessible via the loop. Consider the following two scenarios for locating the array’s smallest element.

Algorithm POOR_FIND_MIN

k ← 0
for i ← 1 to n do
  if A[i] < A[k] then 
    k ← i
  end
end
Min ← A[k]

An efficient version of this algorithm would be:

Algorithm EFFICIENT_FIND_MIN

Min ← A[0]
for i ← 1 to n do
  if A[i] < Min then
    Min ← A[i]
    k ← i
  end
end
Min ← A[k]

The POOR_FIND_MIN algorithm requires two array accesses for each comparison, whereas EFFICIENT_FIND_MIN needs only one. Arithmetic on the array needs to address the calculation on each array access.

EFFICIENT_FIND_MIN compares A[i] with constant Min, which reduces the array access by a factor of two

Late termination

Sometimes, inefficiency in the program is also introduced due to unnecessary tests. The program keeps iterating after producing useful results. Consider the problem of linear search.

Algorithm POOR_LINEAR_SEARCH(A, Key)

Index ← -1
for i ← 1 to n do
  if A[i] == key then
    Index ← i;
  end
end

if Index == -1 then
  print “Key not found”
else
  print “Key found on index i”
end

An efficient version of this algorithm would be:

Algorithm EFFICIENT_LINEAR_SEARCH(A, Key)

flag ← 0
for i ← 1 to n do
  if A[i] == key then
    flag ← 1
    break
  end
end

if flag == 0 then
  print “Key not found”
else
  print “Key found on index i”
end

POOR_LINEAR_SEARCH goes on to iterate n times Key is found at the first location. whereas EFFICIENT_LINEAR_SEARCH breaks the loop once the Key is found, which makes it more efficient.

---

Additional Resource: Problems, Solutions and Tools. Click to read.

Short Questions:

Q: Suggest a few things to improve the efficiency of the code

We shall consider the following things while we write a code, to make it effective and faster:

• Remove redundant operations
• Referencing Array
• Late termination