CS221 Algorithms: Algorithm Analysis

• The presentation is for CS221 Algorithms and Complexity by Junar A. Landicho at the USTP CDO Department of Computer Science.
• The topic is Topic 1: Introduction to Algorithm Analysis.

Course Objectives

• Understand the basics of algorithm analysis including time and space complexity.
• Learn about asymptotic notation including Big O, Big omega, and Big theta, and their application in analyzing algorithm efficiency.
• Explore best, worst, and average-case analysis and their significance in evaluating algorithm performance.

Time Complexity

• Time complexity measures the amount of time an algorithm takes to complete as a function of the size of its input.
• Big O notation (O()) represents the time complexity, providing an upper bound on the growth rate of the algorithm.
• A linear search algorithm has a time complexity of O(n), where 'n' is the size of the input array.

Space Complexity

• Space complexity measures the amount of memory an algorithm requires to execute as a function of the size of its input.
• It can also be represented using Big O notation.
• The space complexity of a simple iterative algorithm that doesn't use any additional data structures might be O(1), indicating constant space complexity.

Time and Space Complexities

• Time and space complexities are performance characteristics describing how the time or space requirements of an algorithm grow with respect to the size of the input.
• These complexities are often represented by functions that indicate how the algorithm's runtime or memory usage increases as the input size increases.
• Space complexity is typically expressed using Big O notation, which provides an upper bound on the worst-case memory usage of an algorithm.
• Time and space complexities themselves are not functions, they are often represented by functions to show how performance or memory usage scales with the input size.
• These functions help analyze and compare the efficiency and resource usage of different algorithms.

Asymptotic Notation

• Asymptotic notation includes O, Ω, Θ, o, and ω.
• Used to describe the running times of algorithms.
• Exact running time is often expressed as Θ(n²).
• Defined for functions whose domain is the set of natural numbers, N.
• Determine sets of functions and compare two functions.

Big O Notation

• f(n) = O(g(n)) means c * g(n) is an upper bound on f(n).
• There exists some constant c such that f(n) is always ≤ c * g(n), for large enough n.

Big O Major Types of Complexities (Time and Space)

• Constant functions, f(n) = 1.
  • Performance remains constant regardless of the size of the input.
  • Accessing an element in an array by index, basic arithmetic operations, adding or removing an element from the beginning or the end of an array if the array size is known are examples.
• Logarithmic functions, f(n) = log n.
  • Performance grows logarithmically with the size of the input.
  • Binary search algorithm, operations on binary trees are examples.
• Linear functions, f(n) = n.
  • Performance grows linearly with the size of the input.
  • Linear search algorithm, iterating through all elements of an array, finding the maximum or minimum element in an unsorted array are examples.
• Superlinear functions, f(n) = n log n.
  • Performance grows in between linear and logarithmic time with the size of the input.
  • Merge sort, quick-sort (average-case time complexity), heap sort, and some divide-and-conquer algorithms are examples.
• Quadratic functions, f(n) = n².
  • Performance grows quadratically with the size of the input.
  • Selection sort, insertion sort, bubble sort, brute-force algorithms with nested loops are examples.
• Cubic functions, f(n) = n³.
  • Performance grows cubically with the size of the input.
  • Matrix multiplication using the naive approach and brute-force algorithms with three nested loops are examples.
• Exponential functions, f(n) = c to the power of n for a given constant c > 1.
  • Performance grows exponentially with the size of the input.
  • Recursive algorithms with exponential growth, such as the naive recursive approach to the Fibonacci sequence, brute-force algorithms with recursive backtracking are examples.
• Factorial functions, f(n) = n!.
  • Runtime grows factorially with the size of the input.
  • Brute-force algorithms for permutation problems and brute-force algorithms for subset or combination problems are examples.
• 3n^2 – 100n + 6 = O(n²) because 3n^2 > 3n^2 -100n + 6, when c = 3
• 3n^3 – 100n + 6 = O(n³) because n^2 > 3n^2 -100n + 6 when n >3, c = 1
• 3n^3 – 100n + 6 ≠ 0(n³) because for any c, c x n < 3n^2> 3n^2 -100n + 6 when n > c

Big Omega Notation

• f(n) = Ω(g(n)) means c * g(n) is a lower bound on f(n).
• There exists some constant c such that f(n) is always ≥ c * g(n), for all n ≥ no.
• Steps to calculate Big - Omega (Ω) Includes:
  • Break up the program into smalle segments
  • Find the number of operations performed for each segment, in terms of the input size, assuming the input is one that produces the least amount of time
  • Add up all the operations and simplify it , f(n)
  • Remove constants, and choose the term having the least order, or any other function that is alwasy less than f(n) when N tends to infinity, let say g(n), therefore, Big-Omega of f(n), is Ω(g(n))

Relationship with Big O

• If a function f(n) is in Ω(g(n)), it implies that f(n) is also in O(g(n)), but not necessarily vice versa.
• Big Omega notation provides a stronger guarantee than Big O notation, representing a lower bound on the growth rate of a function.
• Big Omega notation indicates the best-case scenario or minimum rate of growth.
• Big O notation indicates possible worst case scenario.
• Big Omega provides a stronger guarantee than Big O because it offers a lower bound, ensuring that the function grows at least as fast as the specified bound for large input sizes.

Big Ω Major Types of Complexities (Time and Space)

• Linear Functions (Ω(n)):
  • A linear search algorithm is an example.
  • Best-case scenario: The search key is found at the beginning of the array.
  • Lower bound: The algorithm must examine each element at least once, indicating a linear growth rate.
  • Space: The amount of memory used scales linearly with the input, resulting in a space complexity of Ω(n).
• Quadratic Functions (Ω(n²)):
  • Selection sort is an example.
  • Best-case scenario: The input array is already sorted.
  • Lower bound: Even in the best-case scenario, the algorithm must compare each pair of elements at least once, indicating a quadratic growth rate.
  • Space: The memory required by the matrix increases quadratically as input size increases, resulting in a space complexity of Ω(n²).
• Logarithmic Functions (Ω(log n)):
  • Binary search algorithm is an example.
  • Best-case scenario: The search key is found at the middle of the array.
  • Lower bound: The algorithm divides the search space in half with each comparison, indicating a logarithmic growth rate. -Space: Logarithmic space complexity isn't commonly encountered in practice because it typically involves a recursive algorithm with a logarithmic depth in its call stack. Logarithmic space complexity in terms of big Omega notation implies space usage grows logarithmically with the size of the input.

Comparison to Big O and Big Omega

• Big O notation (O) represents an upper bound. Big Omega notation (Ω) represents a lower bound. Big Theta notation (Θ) combines both upper and lower bounds.
• If a function f(n) is in Θ(g(n)), it implies that f(n) is also in both O(g(n)) and Ω(g(n)), indicating a tight bound on its growth rate.
• 3n^2 – 100n + 6 = Ω(n²), because 2n² < 3n2 – 100n + 6 when n > 100 becuse c=2
• 3n^2-100n+6Ω ≠ Ω(n³), because 3n^2-100n+6<n³ when n>3, c=3
• 3n^2 -100n+6 = Ω(n), because cn < 3n² -100n+6 when n > 100c
• 3n2 – 100n + 6 = Ω(n²) because 2n² < 3n2 -100n + 6, c = 2
• 3n3 – 100n + 6 = Ω(n³) because 3n² < 3n² -100n + 6 when n >3, c=3 3n3 – 100n + 6 ≠ Ω(n³) because for c x n < 3n2> 3n2 -100n + 6 c

Big Theta Notation

• f(n) = Θ(g(n)) means c₁ ⋅ g(n) is an upper bound on f(n) and c₂ ⋅ g(n) is a lower bound on f(n), for all n ≥ n₀
• There exist constants c₁ and c₂ such that f(n) ≤ c₁ ⋅ g(n) and f(n) ≥ c₂ ⋅ g(n), meaning g(n) provides a nice, tight bound on f(n)

Big Theta Major Types of Complexities (Time and Space)

• Constant Functions (Θ(1)):
  • Constant time complexity (Θ(1)) means that the time taken to execute the function remains constant, regardless of the size of the input.
  • Regardless of how large the input is, the time taken by the algorithm does not change.
  • Examples include basic arithmetic operations, accessing an element in an array or list with a known index, or performing a simple assignment operation.
    • Space: Returning a constant value, performing a fixed number of operations regardless of the input size, or using a constant number of variables
• Linear Functions (Θ(n)):
  • Linear time complexity (Θ(n)) means that the time or space taken to execute the function grows linearly with the size of the input.
  • As the input size increases by 'n', the time taken to execute the function increases proportionally.
  • Examples include iterating through an array or list once, finding the maximum or minimum element in an array, or performing a linear search.
    • Space: Creating an array or list of size 'n' or storing input data in an array or list..
• Quadratic Functions (Θ(n²)):
  • The time taken to execute the function grows quadratically with the size of the input.
  • As the input size 'n' increases, the time taken by the algorithm increases proportional to the square of the input size.
  • Examples include nested loops where each loop iterates over the entire input, such as bubble sort, selection sort, and some naive matrix multiplication algorithms. - Space complexity includes creating a 2D matrix where both dimensions are proportional to the input size, or storing all pairs of elements from an input list.
• 3n2 – 100n + 6 = O(n²), because both O and Ω apply.
• 3n² - 100n + 6 ≠ Θ(n³), because only O applies.
• 3n² - 100n + 6 ≠ Θ(n), because only Ω applies.

Working with Notations

• The sum of two functions is governed by the dominant one.
  • O(f (n)) + O(g(n)) → O(max(f (n), g(n))).
  • Ω(f (n)) + Ω(g(n)) → Ω(max(f (n), g(n))).
  • Θ(f (n)) + Θ(g(n)) → Θ(max(f (n), g(n))).
• This is very useful in simplifying expressions, since it implies that n3 + n2 + n + 1 = O(n³). Everything is small potatoes besides the dominant term.
• Suppose f(n) = O(n²) and g(n) = O(n²). This implies that f(n) + g(n) = O(n²) as well.

Multiplying Functions

• Multiplication is like repeated addition. Consider multiplication by any constant c > 0, be it 1.02 or 1,000,000.
• Multiplying a function by a constant cannot affect its asymptotic behavior.
  • O(c ⋅ f(n)) → O(f(n)).
  • Ω(c ⋅ f(n)) → Ω(f(n)).
  • Θ(c ⋅ f(n)) → Θ(f(n)).
• C must be strictly positive (i.e., c > 0) to avoid any funny business, since we can wipe out even the fastest growing function by multiplying it by zero.
• On the other hand, when two functions in a product are increasing, both are important.
  • O(f (n)) * O(g(n)) → O(f (n) * g(n)).
  • Ω(f (n)) * Ω(g(n)) → Ω(f (n) * g(n)).
  • Θ(f (n)) * Θ(g(n)) → Θ(f (n) * g(n)).

Little o(0)

• f(n)=o(g(n)) means that f(n) grows strictly slower than g(n) as n approaches infinity.
• For every positive constant c > 0, there exists a value no such that for all n > no, f(n) is strictly less than c⋅g(n)
• In simpler terms, f(n) grows much faster than g(n), and the ratio of f(n) to g(n) approaches zero as n grows larger.
• n² is o(n³), because n² grows much slower than n³ as n increases

Little omega

• f(n)=w(g(n)) means that f(n) grows strictly faster than g(n) as n approaches infinity.
• For every positive constant c > 0, there exists a value no such that for all n > no, f(n) is strictly greater than c⋅g(n)
• In simpler terms, f(n) grows much faster than g(n), and the ratio of f(n) to g(n) approaches infinity as n grows larger.
• n³ is w(n²), because n³ grows much faster than n² as n increases.

Esoteric Functions

• Refer to unusual or non-standard functions that are not commonly encountered in mainstream algorithm design or analysis.
• These functions are often used in theoretical contexts, puzzle-solving, or as a way to explore the boundaries of computation rather than practical application.
• Understanding their growth rates can provide insights into theoretical computer science

Inverse Ackerman's function

• Function f(n) = a(n)
• This function arises in the de- tailed analysis of several algorithms, most notably the Union-Find data structure.
• Unlike the constant function f(n) = 1, it eventually gets to infinity as n → ∞, but it certainly takes its time about it. The value of a(n) < 5 for any value of n that can be written in this physical universe.

Esoteric Functions

• f(n) = log log n
  • The "log log" function= the logarithm of the logarithm of n.
  • One has of how it might arise example is is doing a binary search on a sorted array of only log n items. Log log only applies if it will be a sorted array of only log n iterations
• f (n) = log n/ log log n
  • This function grows little slower than log n because it is divided of a very quickly growing function
  • One has to see where this arises, consider the leaf a rooted tree log n/ Log Log and is used to find the height of degree

Esoteric Functions

• f (n) = log^2 n

  • is the product of log functions-i.e., (log n) × (log n). This might happen if we needed to count the bits looked during a binary search with n bits

• Each of log n bits.

• The "log squared" function is in intricate data structures, where each one in say binary tree represents another data structure that can be sorted in different order.

• f(n) = √n

  • the square root is not that esoteric, but represents the class of sublineal problems as it can be done by n1/2

Sublinear Polynomials

• Such functions arise in building d-dimensional grids that contain n points. -A √n × √n square has area n, and an n1/3 × n1/3 × n1/3 cube has volume n. -In general, a d-dimensional hypercube of length n¹/d on each side has volume d.

• f(n) = n(1+ε)

    -      Term begin with the is symbol to make a way to use 2c
  

Best-Case Analysis

• Definition: Average-case analysis assesses the performance of an algorithm based on the expected behavior when inputs are randomly distributed or follow a specific probability distribution.
• Insights: Average-case analysis offers a more realistic perspective on algorithm performance by considering a range of input scenarios and their likelihood of occurrence.
• Examples: Quicksort typically demonstrates its average-case performance when the input array is randomly shuffled, showcasing its efficient partitioning and sorting strategy.

Average-Case Analysis

• The performance of an algorithm based on the expected behavior when inputs are randomly distributed or follow a specific probability distribution.
• Insights: Gives a more realistic perspective on algorithm performance by considering a range of input scenarios and their likelihood of occurrence. -Examples: Quicksort shows its average-case performance when the input array is randomly shuffled, and its efficient partitioning.

Worst-Case Analysis

• Worst-case analysis studies the performance of an algorithm under the most unfavorable conditions, where inputs increase time or space complexity. Highlights possible vulnerabilities and performance bottlenecks in algorithms, which helps risk control and algorithm selection.
• Insertion Sort its worst-case performance when the input array is sorted in reverse order, leading to quadratic time complexity due to frequent element shifts.