Algorithm Analysis

Definition of an Algorithm: * An algorithm is defined as a specific set of instructions followed to solve a particular problem. * A single problem can have multiple solutions (different algorithms). * Algorithms are platform and language independent; they can be implemented using various programming languages (e.g., C++) and run on different platforms.
Correctness of Algorithms: * An algorithm must solve the intended problem correctly. * Example: In a sorting algorithm, correctness implies the algorithm works even if: 1. The input is already sorted. 2. The input contains repeated elements.
Algorithmic Performance Aspects: * Time: Determined by the execution of instructions. Analysis focuses on how fast an algorithm performs and factors affecting its runtime. * Space: Determined by the data structures used. Analysis focuses on which data structures are employed and how they affect runtime. * Course Focus: This study material emphasizes estimating and reducing the time required for an algorithm.

Goal of Analysis: To provide tools to analyze the efficiency of different problem-solving methods independently of specific environments.
The Naïve Approach: This involves implementing algorithms (e.g., in C++) and running them to compare time requirements. This approach has significant difficulties: * Implementation Sensitivity: Comparing running times often compares the quality of the code (programming style) rather than the inherent efficiency of the algorithm. * Computer Dependency: Running times are affected by the specific hardware used. * Data Dependency: Results may vary based on the specific data used for the test.
Mathematical Techniques: Modern analysis employs techniques that are independent of implementation, computers, or specific data. 1. Count the number of significant operations in a solution to assess efficiency. 2. Express efficiency using growth functions.

Operation Cost: Each operation in an algorithm has a specific cost ( $c$ ) represented in time units.
Sequence of Operations: Total cost is the sum of individual costs. * Example: count = count + 1; (cost $c_1$ ) followed by sum = sum + count; (cost $c_2$ ) results in Total Cost = $c_1 + c_2$ .
Simple If-Statement Analysis: * if (n < 0) (cost $c_1$ , 1 time) * absval = -n (cost $c_2$ , 1 time) * else absval = n; (cost $c_3$ , 1 time) * Total Cost: $\text{Total Cost} \ngtr c_1 + \text{max}(c_2, c_3)$ .
Simple Loop Analysis: * i = 1; ( $c_1$ , 1 time) * sum = 0; ( $c_2$ , 1 time) * while (i <= n) ( $c_3$ , $n+1$ times) * i = i + 1; ( $c_4$ , $n$ times) * sum = sum + i; ( $c_5$ , $n$ times) * Total Cost Formulation: $\text{Total Cost} = c_1 + c_2 + (n+1) \times c_3 + n \times c_4 + n \times c_5$ . * Result: The time required is proportional to $n$ .
Nested Loop Analysis: * i=1; ( $c_1$ , 1 time) * sum = 0; ( $c_2$ , 1 time) * while (i <= n) ( $c_3$ , $n+1$ times) * j=1; ( $c_4$ , $n$ times) * while (j <= n) ( $c_5$ , $n \times (n+1)$ times) * sum = sum + i; ( $c_6$ , $n \times n$ times) * j = j + 1; ( $c_7$ , $n \times n$ times) * i = i + 1; ( $c_8$ , $n$ times) * Total Cost Formulation: $\text{Total Cost} = c_1 + c_2 + (n+1) \times c_3 + n \times c_4 + n \times (n+1) \times c_5 + n^2 \times c_6 + n^2 \times c_7 + n \times c_8$ . * Result: The time required is proportional to $n^2$ .

Loops: The running time of a loop is at most the running time of the statements inside the loop multiplied by the number of iterations.
Nested Loops: The running time is the running time of the statement in the innermost loop multiplied by the product of the sizes of all surrounding loops.
Consecutive Statements: Add the running times of each individual consecutive statement.
If/Else: The running time is never more than the time of the initial test plus the larger of the running times of the branch statements ( $S_1$ and $S_2$ ).

Problem Size ( $n$ ): Time requirements are measured as a function of problem size. * Example: Number of elements in a list for sorting; number of disks for Towers of Hanoi.
Proportional Time: If Algorithm A requires $5 \times n^2$ units and Algorithm B requires $7 \times n$ units, A is proportional to $n^2$ and B is proportional to $n$ .
Growth Rate: The proportional time requirement of an algorithm. Growth rates allow for efficiency comparisons.
Big O Notation Definition: Algorithm A is order $f(n)$ —denoted as $O(f(n))$ —if constants $k$ and $n_0$ exist such that A requires no more than $k \times f(n)$ time units for a problem size $n \ngtr n_0$ . * The condition $n \ngtr n_0$ formalizes the concept of "sufficiently large problems."
Example of Order Calculation: * Requirement: $n^2 - 3 \times n + 10$ seconds. * If $k = 3$ and $n_0 = 2$ : $3 \times n^2 > n^2 - 3 \times n + 10$ for all $n \ngtr 2$ . * Conclusion: The algorithm is $O(n^2)$ .

Function	Name	Description
$c$	Constant	Time is independent of problem size.
$\text{log}(N)$	Logarithmic	Time increases slowly as size increases.
$\text{log}^2N$	Log-squared	Higher order than logarithmic.
$N$	Linear	Time increases directly with problem size.
$N \text{ log } N$	$N \text{ log } N$	Increases more rapidly than linear.
$N^2$	Quadratic	Time increases rapidly with problem size.
$N^3$	Cubic	Increases more rapidly than quadratic.
$2^N$	Exponential	Increases too rapidly to be practical for large sizes.

Growth comparison for varying $n$ values: * When $n = 10$ : * $\text{log}_2n \ngtr 3$ * $n \ngtr 10$ * $n \times \text{log}_2n \ngtr 30$ * $n^2 \ngtr 100$ * $n^3 \ngtr 1,000$ * $2^n \ngtr 1,000$ * When $n = 1,000,000$ : * $\text{log}_2n \ngtr 19$ * $n \ngtr 10^6$ * $n \times \text{log}_2n \ngtr 10^7$ * $n^2 \ngtr 10^{12}$ * $n^3 \ngtr 10^{18}$ * $2^n \ngtr 10^{301,030}$
Time increase when problem size doubles (from size 8 to size 16 if time at size 8 is 1s): * $O(1) \rightarrow 1 \text{ second}$ * $O(\text{log}_2n) \rightarrow \frac{1 \times \text{log}_216}{\text{log}_28} = \frac{4}{3} \text{ seconds}$ * $O(n) \rightarrow \frac{1 \times 16}{8} = 2 \text{ seconds}$ * $O(n \times \text{log}_2n) \rightarrow \frac{1 \times 16 \times \text{log}_216}{8 \times \text{log}_28} = \frac{8}{3} \text{ seconds}$ * $O(n^2) \rightarrow \frac{1 \times 16^2}{8^2} = 4 \text{ seconds}$ * $O(n^3) \rightarrow \frac{1 \times 16^3}{8^3} = 8 \text{ seconds}$ * $O(2^n) \rightarrow \frac{1 \times 2^{16}}{2^8} = 2^8 = 256 \text{ seconds}$

Ignore Low-Order Terms: If an algorithm is $O(n^3 + 4n^2 + 3n)$ , it is considered $O(n^3)$ . Only the highest-order term is used.
Ignore Multiplicative Constants: If an algorithm is $O(5n^3)$ , it is considered $O(n^3)$ .
Combination Rules: * $O(f(n)) + O(g(n)) = O(f(n) + g(n))$ . * Example: $$O(n^3