Program Performance: Algorithms and Efficiency

Program Performance

• Factors determining program performance include algorithms, data structures, hardware, compiler, programming language, and operating system

Algorithm Efficiency

• Algorithm efficiency considers the amount of memory used (space complexity)
• The amount of time it takes (time complexity), and is dependent on the input size

Algorithm Analysis

• Algorithm analyses include worst-case, average-case, and best-case scenarios
• Worst-case analysis usually focuses on the maximum time an algorithm takes for any input of size n
• Average-case analysis considers the expected time of an algorithm over all inputs of size n
• Best-case analysis is not reliable and may involve a slow algorithm that performs well on specific inputs

Basic Operation

• The basic operation contributes the most to the running time of the algorithm
• Basic operations include arithmetic operations (addition, subtraction, multiplication, division, modulus) and comparison operations (if)
• The total time is calculated by multiplying the time of the basic operation by the number of times it is repeated

Input Size Measure Examples

• Key comparison is a basic operation when searching for a key in a list
• The input size is the number of list items (n)
• Multiplication of two numbers is a basic operation when multiplying two matrices
• The input size is metric dimensions or the total number of elements
• Division is a basic operation when checking the primality of a given integer
• The input size is the number of digits in the binary representation
• Visiting a vertex or traversing an edge is a basic operation for typical graph problems
• The input size is the number of vertices and/or edges

Big O Notation

• Big O notation estimates the efficiency of a function or algorithm
• It indicates the time it takes for the function or algorithm to execute

Big O Constants

• Constants (Big O = 1)
• For equations, focus on the largest contributing factor
• Common complexities include bounded (by a constant) time O(1), logarithmic time O(log₂N), linear time O(N), Nlog₂N time O(Nlog₂N), quadratic time O(N²), cubic time O(N³), exponential time O(2^N)

Analyzing Code Examples

• In if statements, the condition that is triggered changes the value or calculation, resulting in different behavior depending on whether the condition is true or false

• Analyzing for loops involve determining whether they involve a single loop

• Two non-nested loops (addition of complexities)

• Two nested loops (multiplication of complexities)

• Note, if a for loop involves division, multiplication or a modulus then the Bix O is log n

Time Complexity Questions

• Any algorithm must possess a finite number of steps, series of concrete steps and be correct and terminated
• For the following function, the most important term is the largest contributing one
• Examples:
  • time complexity for nested lookups in n^2
  • The better computing time is the smaller number
  • Any function with constant growth rate has a compelxity of O(1)
  • It is important to identify the rate increasing function for Big O analysis
  • Lookups can use iterative, recorruve, quick or binary operations