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 

Note (2): Calling a function/method excludes operations executed within the function/method.
Focusing on WorstCase 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 averagecase analysis by taking the average of the running time over all possible inputs of the same size.
 Averagecase 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 worstcase analysis.
 Easier to calculate since we only need to identify the worstcase input.
 Also, designing for the worstcase leads to the algorithm doing well on every input.
Note (3): Focusing on the bestcase 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:
 Identify each primitive operation in the pseudocode
 Count how many times each primitive operation is executed
 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 worstcase 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 Cstyle 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 collectionbased or iteratorbased loops and use the concept of iterables and iterators to perform the looping operation as opposed to the index based approach used in Cstyle loops. Under the hood Python is actually using two builtin 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 worstcase 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$