Primitive Operations

What is a Primitive Operation?

• A basic computation performed by an algorithm
• Identifiable in pseudocode
• Largely independent from the programming language being used
• Assumed to have a constant execution time
• Exact definition is not important

Note (1): As long as we correctly identify the growth rate of the algorithm, the exact definition of a primitive operation is not important since we can model the behavior of the alogrithm by using asymptotic analysis which we'll discuss how to do in a future notebook.

Examples of Primitive Operations

Primitive Operation	Pseudocode Example	Equivalent Python Code
Assigning a value to a variable	x $\leftarrow$ 5	x = 5
Performing an arithmetic operation	$a^3 + b/2$	a**3 + b/2
Comparing two numbers	$i \geq j$	i >= j
Accessing a single element in a Python list by index	A[0]	A[0]
Calling a function/method	findMax(A)	findMax(A)
Returning from a function/method	return y	return y

Note (2): Calling a function/method excludes operations executed within the function/method.

Focusing on Worst-Case Input

• An algorithm might run faster on some inputs than other inputs even if the inputs being compared are the same size.

  • For example, finding the smallest number in a list of size, $n$, that has been sorted in inreasing order vs finding the smallest number in a list of size, $n$, that is sorted randomly.
• To factor in this possibilty we can perform an average-case analysis by taking the average of the running time over all possible inputs of the same size.
• Average-case analysis is very useful, but often difficult to determine since it requires defining a probability distribution over the set of inputs.

• Therefore, we'll focus on charaterizing the running time of an algorithm using worst-case analysis.

  • Easier to calculate since we only need to identify the worst-case input.
  • Also, designing for the worst-case leads to the algorithm doing well on every input.

Note (3): Focusing on the best-case input is usually useless since it requires ideal conditions for the algorithm to perform in an acceptable manner.

Counting Primitive Operations

• To determine the running time, $t$, of an algorithm as a function of the input size, $n$, we need to perform the following steps:

  1. Identify each primitive operation in the pseudocode
  2. Count how many times each primitive operation is executed
  3. Calculate the running time by summing the counts of primitive operations

Note (4): We're assuming the running times of different primitive operations will be fairly similar, so the calculated running time, $t$, will be proportional to the actual running time of an algorithm.

Counting Primitive Operations Examples

Ex. 1) Find the maximum element in a list

Algorithm findMax(A)
  Input list A of n integers
  Output the maximum element of A

  currentMax $\leftarrow$ A[0]
  for currentValue $\leftarrow$ nextElementInA (starting from the 1st element in A) to EndOfA do
    if currentValue > currentMax then
      currentMax $\leftarrow$ currentValue
  return currentMax

• Line 1, currentMax $\leftarrow$ A[0], is $2$ operations since we're accessing a single element in a list by index and assigning a value to a variable.
• Line 2, for currentValue $\leftarrow$ nextElementInA (starting from the 1st element in A) to EndOfA do, is $c_1 + c_2n$ operations where $c_1$ represents the constant number of primitive operations associated with the initializing and the terminating of the for loop, and $c_2$ represents the number of primitive operations associated with the maintenance of the iterator which is done $n$ times, so the total amount of maintenance of the iterator is $c_2n$ (see Note (5) for why specific values for $c_1$ and $c_2$ are not given).
• Line 3, if currentValue > currentMax then, is $n$ operations since we're comparing two numbers during each iteration of the loop.
• Line 4, currentMax $\leftarrow$ currentValue, consists of $n$ operations, since we're assuming worst-case input which means currentMax will be updated on each iteration of the loop.
• Line 5, return currentMax, consists of $1$ operation since we're only returning a value from a function.

Therefore, the running time of the algorithm is:

$t = 2 + c_1 + c_2n + n + n + 1 = 3 + c_1 + c_2n + 2n$

Note (5): Explicit values for $c_1$ and $c_2$ are not given because the number of primitive operations being executed in a Python for loop, e.g., for i in list is not as obvious as say a C-style for loop, e.g., for(i = 0; i < 10; i++) since the implementation details are being abstracted away to allow for easier readability and usability. Python for loops are referred to as collection-based or iterator-based loops and use the concept of iterables and iterators to perform the looping operation as opposed to the index based approach used in C-style loops. Under the hood Python is actually using two built-in functions iter() and next() to implement the for loop which we can discuss in more detail in a future blog post and video.

Note (6): Not knowing the exact values for $c_1$ and $c_2$ is also not entirely necessary because as mentioned earlier we can use asymptotic analysis to model the behavior of our algorithms as long as we correctly identify the growth rate.

Note (7): Even though we'll ultimately be using asymptotic analysis to model our algorithms if you're interested in examining the primitive operations being executed in a Python program in more detail you can use the dis module which is the disassembler for Python bytecode. This allows us to examine the set of instructions used by the Python virtual machine. A .pyc file is actually the compliled bytecode. However, for our purposes we don't need to concern ourselves with all of the under the hood details. If anyone is interested though we can also make a future blog post or video discussing the dis module in more detail.

Ex. 2) Sum all of the elements in a list

Algorithm calculateSum(A)
  Input list A of n integers
  Output sum of all the elements of A

  currentSum $\leftarrow$ 0
  for valueToBeAdded $\leftarrow$ nextElementInA (starting from the 1st element in A) to EndOfA do
    currentSum $\leftarrow$ currentSum + valueToBeAdded
  return currentSum

• Line 1, currentSum $\leftarrow$ 0, is $1$ operation since we're assigning a value to a variable.
• Line 2, for valueToBeAdded $\leftarrow$ nextElementInA (starting from the 1st element in A) to EndOfA do, is once again $c_1 + c_2n$ operations where $c_1$ once again represents the constant number of primitive operations associated with the initializing and the terminating of the for loop, and $c_2$ once again represents the number of primitive operations associated with the maintenance of the iterator which is done $n$ times, so the total amount of maintenance of the iterator is $c_2n$.
• Line 3, currentSum $\leftarrow$ currentSum + valueToBeAdded, is $2n$ operations since we're performing an arithmetic operation and assigning the result to a variable during each iteration of the loop.
• Line 4, return currentSum, consists of $1$ operation since we're only returning a value from a function.

Therefore, the running time of the algorithm is:

$t = 1 + c_1 + c_2n + 2n + 1 = 2 + c_1 + c_2n + 2n$

Ex. 3) Calculate the average of the elements in a list

Algorithm calculateAverage(A)
  Input list A of n integers
  Output average of all the elements of A

  currentSum $\leftarrow$ 0
  for valueToBeAdded $\leftarrow$ nextElementInA (starting from the 1st element in A) to EndOfA do
    currentSum $\leftarrow$ currentSum + valueToBeAdded
  return currentSum/length of A

• Line 1, currentSum $\leftarrow$ 0, is $1$ operation since we're assigning a value to a variable.
• Line 2, for valueToBeAdded $\leftarrow$ nextElementInA (starting from the 1st element in A) to EndOfA do, is once again $c_1 + c_2n$ operations for the same reasons as the previous examples.
• Line 3, currentSum $\leftarrow$ currentSum + valueToBeAdded, is $2n$ operations since we're once again performing an arithmetic operation and assigning the result to a variable during each iteration of the loop.
• Line 4, return currentSum/length of A, consists of $3$ operations since we'll be calling the len() function to get the length of list A, performing an arithmetic operation, and returning a value from a function.

Therefore, the running time of the algorithm is:

$t = 1 + c_1 + c_2n + 2n + 3 = 4 + c_1 + c_2n + 2n$

Ex. 4) Find how many elements in a list are even

Algorithm findNumberOfEvenElements(A)
  Input list A of n integers
  Output the number of elements in list A that are even

  numberOfEvenElements $\leftarrow$ 0
  for currentValue $\leftarrow$ nextElementInA (starting from the 1st element in A) to EndOfA do
    if currentValue mod 2 = 0 then
      numberOfEvenElements $\leftarrow$ numberOfEvenElements + 1
  return numberOfEvenElements

• Line 1, numberOfEvenElements $\leftarrow$ 0, is $1$ operation since we're assigning a value to a variable.
• Line 2, for currentValue $\leftarrow$ nextElementInA (starting from the 1st element in A) to EndOfA do, is once again $c_1 + c_2n$ operations for the same reasons as the previous examples.
• Line 3, if currentValue mod 2 = 0 then, consists of $2n$ operations since we're performing an arithmetic operation and then comparing the result with 0 during each iteration of the loop.
• Line 4, numberOfEvenElements $\leftarrow$ numberOfEvenElements + 1, consists of $2n$ operations since we're assumuing the worst-case input which means each element in A is even, so we're performing an arithmetic operation and assigning the result to a variable during each iteration of the loop.
• Line 5, return numberOfEvenElements, consists of $1$ operation since we're only returning a value from a function.

Therefore, the running time of the algorithm is:

$t = 1 + c_1 + c_2n + 2n + 2n + 1 = 2 + c_1 + c_2n + 4n$