Introduction to Theoretical Analysis

Benefits of Theoretical Analysis

• Can evaluate the speed of an algorithm independently of the hardware & software environment
• Able to use a pseudocode desricption of an algorithm instead of an implementation
• Characterize the running time as a function of the input size, $n$
• Takes into account all possible inputs

What is Pseudocode?

• High-level description of an algorithm
• Preferred notation for describing algorithms
• Designed for human understanding
• Suppresses unimportant details
• Hides program design issues

Common Pseudocode Notation

• Function/Method Declaration
    Algorithm method(Argument one, Argument two, ...)
    Input - indicates the input to the algorithm
    Output - indicates the output of the algorithm
• Method Call
    var.method(Argument one, Argument two, ...)
• Return Value
    return expression

• Control Flow

  • if ... then ... else ... - indicates a decision the algorithm must make, i.e., if a condition is true then do something if the condition is false then do something else
  • while ... do ... - indicates a top tested loop, i.e., first evaluate the condition and if the condition evaluates to false, then the looping ends. If the condition evaluates to true, then do one iteration of the loop, then repeat the loop while the condition is true.
  • for ... do ... - indicates a loop where we already know how many times the loop will be executed
  • repeat ... until ... - indicates a bottom tested loop, i.e., do one iteration of the loop then evaluate the condition. If the condition evaluates to false, then repeat. If the condition evaluates to true, the looping ends.
• Expressions
    $\leftarrow$ Assignment
      (like $=$ in Python)

    $=$ Equality testing
      (like $==$ in Python)

    $n^2$ Exponentiation
      (like $n**2$ in Python)

    $\geq$ greater than or equal to
      (like $>=$ in Python)

    $\leq$ less than or equal to
      (like $<=$ in Python)

Note (1): Other mathematical formatting can appear and the corresponding Python operations can be found in the official documentation.

Pseudocode 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

Ex. 2) Find the minimum element in a list

Algorithm findMin(A)
  Input list A of n integers
  Output the minimum element of A

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

Ex. 3) 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

Ex. 4) Multiply all of the elements in a list

Algorithm calculateProduct(A)
  Input list A of n integers
  Output multiplication of all the elements of A

  currentProduct $\leftarrow$ 1
  for multiplier $\leftarrow$ nextElementInA (starting from the 1st element in A) to EndOfA do
    currentProduct $\leftarrow$ _currentProduct _ multiplier
  return *currentProduct\

Note (2): Since the purpose of these examples is to familiarize us with writing pseudocode, the suggested implementations are not optimized.