Compute the Number of Operations in an Algorithm

To compute the number of floating point operations in a numerical algorithm; first, write down your algorithm as pseudocode. Then simply count the number of arithmetic operations that the algorithm is performing (per iteration if the algorithm loops). All operations (addition, subtraction, multiplication, and division) are usually counted to be the same, i.e. 1 flop. This is not exactly true, since multiplication includes several additions and division includes several multiplications when actually executed by a computer. However, we are looking for an estimate here, so it is reasonable to assume that on average, all operations count in the same manner.

Here is an example (just for illustration):

for i = 0 to P

for n = 1 to N (number of elements in array)

B(n) = a(n)*a(n-1) - 2*c(n) + 3

next n

next i

For each n there are 2 multiplications, 1 subtraction, and 1 addition resulting in 4 operations. This loop is executed N times, so there are 4N operations. This is the the order of the algorithm. In this example, its is O(4N) or simply O(N) (constants do not count).

For all iterations, there are 4N(P+1) operations. (remember, when starting the loop from 0 to P, there are P+1 steps).

I posted this article in 2005 in the FAQ section of the CFD-Wiki. You'll find the original post here.

Cite as:
Saad, T. "Compute the Number of Operations in an Algorithm". Weblog entry from Please Make A Note. http://pleasemakeanote.blogspot.com/2008/06/compute-number-of-operations-in.html