[prev] 18 [next]

Counting Primitive Operations

By inspecting the pseudocode …
  • we can determine the maximum number of primitive operations executed by an algorithm
  • as a function of the input size

Example: 

arrayMax(A):
|  Input  array A of n integers
|  Output maximum element of A
|
|  currentMax=A[0]                   1
|  for all i=1..n-1 do               n+(n-1)
|  |  if A[i]>currentMax then        2(n-1)
|  |     currentMax=A[i]             n-1
|  |  end if
|  end for
|  return currentMax                 1
                                     -------
                             Total   5n-2