COMP2211 Lecture: Analyzing Algorithms

Definitions and Rules

• Presented by: Daniel Coore, PhD, University of the West Indies.
• Key topics discussed in the lecture include:
  • Computational Problems
  • Algorithms
  • Computational Complexity
  • Assessment of Algorithms

Working Definitions

Definition (Problem)

A (computational) problem must specify three main components:

• Input: The data that is given or available for processing.
• Output: The data that is required or expected as a result of processing the input.
• Constraints: The limitations or restrictions on the methods that may be used to obtain the output from the input.
  • Example: Compute the square root of an integer n, using hardware that supports only addition, multiplication, subtraction, and division, in addition to standard logic operations (including comparisons).

Definition (Algorithm)

• An algorithm is defined as:
  • A finite sequence of computationally feasible steps that transforms the input into the output while adhering to all specified constraints.
  • An algorithm must also utilize finite time to execute.

Characterizing Algorithms

When analyzing an algorithm, the following properties are essential to consider:

1. Correctness: Does the algorithm produce the correct output for all valid inputs?
2. Time Complexity: How much time does it take to run, generally represented as a function of input size?
3. Space Complexity: How much memory does it utilize during execution?
4. Optimality: Is the algorithm optimal in terms of space or time?

Computational Complexity

• Resource usage, whether time or space, is reported as a function of the size of the input.
• As input size increases, more resources are required to solve problems of that size.
  • Example: Sorting an array.
• The function describing the resource usage is known as the computational complexity of the algorithm.
  • We can specifically assess both time complexity and space complexity.

Assessing Time Complexity

Time Complexity Measurement

• Time complexity is not measured in actual time units.
• Instead, it is assessed by counting the number of basic operations performed over an arbitrary input defined by an unknown size, n:
  • These operations are expressed as functions of n.

Steps to Assess Time Complexity

To assess the time complexity of a given algorithm, follow these three basic steps:

1. Identify Basic Operations: These are the steps that will be counted as a part of the execution.
2. Define Size of Input: Specify what n represents in relation to the input size.
3. Count Basic Operations: Count the operations performed for an arbitrary input of size n. This will be reported as the time complexity, denoted as a function T(n).
4. Analyze Execution Paths: There may be multiple execution pathways depending on input size. The analysis can be segmented into:
   • Best Case: Count the fewest operations performed.
   • Worst Case: Count the maximum number of operations performed.
   • Average Case: Calculate an average count over all possible execution paths.
   • Generally, in this course, default consideration will be towards worst case performance.

Example of Operation Counting

Considering the following example:

def pow1(x, y):
    result = 1
    for i in range(y):
        result = result * x
    return result

• Basic operations used include: {+, -, *, <, range, for iter}.
• Questions to consider:
  1. Do both inputs matter equally?
  2. If not, which one is more significant and why?
  3. What is the function relating input values to the number of basic operations?

Instrumentation of Code for Operation Counting

An example of instrumenting the code to count operations can be:

def pow1(x, y):
    _oc = 0
    result = 1
    _oc += 1  # Initialize
    for i in range(y):
        _oc += 1  # for iterator
        result = result * x
        _oc += 1  # Multiply operation
    return (result, _oc)

Rules for Counting Notation

• Let B be the declared set of basic operations.
• Use the notation Time[E] to denote the time complexity of expression E.
  • Time[E] will indicate the total number of basic operations executed in the sub-expressions within E.
• The value of an expression, after evaluation, is denoted by ⟨E⟩, to avoid double-counting operations.
  • Primitive Data: Time[c] = 0 for constant expressions (e.g., Time[20] = 0, Time["foobar"] = 0).
  • Variable References: Time[var] = 0 (e.g., Time[x] = 0).
  • Primitive Operations: For an operator ◦:
  • If ◦ ∈ B, then Time[E1 ◦ E2] = Time[E1] + Time[E2] + 1.
  • Otherwise, Time[E1 ◦ E2] = Time[E1] + Time[E2].

Compound Constructs

• Sequencing: Time[E1; E2] = Time[E1] + Time[E2]
• Conditional:
  • Time[if Ep: Ec else Ea] = Time[Ep] + Time[Ec] if ⟨Ep⟩ is not false.
  • Time[Ep] + Time[Ea] otherwise.
• Iteration (for loop):
  • Time[for v in Er: Eb] = Time[Er] + Σ_{v ∈ ⟨Er⟩}(Time[Eb] + Time[for iter]).
• Iteration (while loop):
  • Time[while Ec: Eb] =
  • Time[Ec] if ⟨Ec⟩ is false.
  • Time[Ec] + Time[Eb] + Time[while Ec: Eb] otherwise.