Algorithms - Primitive Operations

Primitive Operations are actions the code executes that takes some amount of time. The exact amount of time will vary, based on computer hardware, operating system, etc. But for the most part, on any given machine, each instance of a primitive operation will take the same amount of time as any other. This fact is very useful for Runtime Analysis.

Types of Primitive Operations

Each of the following are one single instance of a Primitive Operation. Remember that each one of these is expected to take roughly the same amount of time.

• Assigning a Value to a Variable
• Calling a Method
• Performing a Basic Arithmetic Operation
• Comparing Two Numbers
• Indexing into an Array
• Following an Object Reference
• Returning from a Method

Example of Counting Primitive Operations within Code

For example, we can look at this pseudocode in which we have an arbitrary array of integers A, and the length of the array n.

1) currentMax ← A[0]
2) for i ← to n do
3)     if currentMax < A[i] then
4)         currentMax ← A[i]
5) return currentMax

We can count the number of Primitive Operations (PO's) in a segment of code by counting line by line. Note that, generally speaking, potentially complicated lines of logic can often be broken down into simpler terms. For example, the single line for loop at line 2:

for i ← to n do

Can be broken down into a three line while loop that's equivalent:

2.a) i ← 1
2.b) while i ≤ n
2.c)    i ← i + 1

Thus giving us this final block of code:

1  ) currentMax ← A[0]
2.a) i ← 1
2.b) while i ≤ n
3  )     if currentMax < A[i] then
4  )         currentMax ← A[i]
2.c)    i ← i + 1
5  ) return currentMax

Breaking it down by line, we have the following table:

Line #	Types of PO's	Total PO Count
1	Assign Value, Index Access	2
2.a	Assign Value	1
2.b	Compare Integers (n+1 times - n times pass, 1 time fails)	n+1
3	Compare Integers, Index Access	2
4	Assign Value, Index Access	2
2.c	Assign Value, Arithmetic	2
5	Return from Method	1

Note that any lines in a loop will occur every time the loop executes. And any lines in an if statement will occur every time the if statement passes. So if we account for that, then line 4 will execute between 0 and n times.

If we assume line 4 executes 0 times, then we can add up the PO's in each line and simplify to get the following result:

[2] + [1] + [n+1] + n([2] + [0] + [2]) + [1]
3 + [n+1] + n(4) + 1
4 + n + 1 + 4n
5n + 5

If we assume line 4 executes n times, then we can add up the PO's in each line and simplify to get the following alternative result:

[2] + [1] + [n+1] + n([2] + [2] + [2]) + [1]
3 + [n+1] + n(6) + 1
4 + n + 1 + 6n
7n + 5

Thus, we have calculated this this segment of code will take between 5n + 5 and 7n + 5 units of time to run, where n will vary, based on the length of the given array. These equations can then be used for evaluating Runtime Analysis.