1_Introduction_AlgorithmsComplexity
Distinguishing Good Algorithms from Bad Algorithms
Criteria for Evaluation
a) By quality of solution
b) By speed
c) By memory consumption
d) By interpretability
Exhaustive Search & Problem Solving (Page 28)
Finite Problems
All real problems are theoretically finite.
Can be solved by exhaustive search over all combinations.
Example Problem: Finding the closest pair of points on a plane.
Algorithm: Compute the distance between all pairs of points.
Measuring Running Time (Page 29)
Running Time as a Characteristic
The main characteristic used to evaluate algorithms is running time or time complexity.
Factors Affecting Running Time:
Depends on:
CPU architecture and power
Input size
Input structure
Units of Measuring Running Time (Page 30)
Elementary Operations:
Function calls
Logical operations (AND, OR, comparison)
Arithmetic operations (+, -, *, /)
Assignment operations (e.g., x = 5)
Accessing array elements by index (e.g., a[i])
Definition of Running Time (Page 31)
Running time for input X is the number of elementary operations performed while processing X.
Example: Sum of Elements in an Array (Pages 32-33)
Input: X = [2, 3, 1, 4, 2]
Initial sum = 0
Algorithm:
For i = 1 to n, sum = sum + X[i]
Output: 12
Count of Elementary Operations:
Assignments: 2
Additions: 5
Accesses: 5
Comparisons: 5
Total Running Time: 27 operations.
Finding a Number in an Array (Pages 34-38)
Input: X = [2, 3, 1, 4, 2], m = 4
Algorithm:
For i = 1 to n, if a[i] = m, return true; return false.
Running Time Calculation: 1 + 4(4) + 1 = 18
In worst-case if not found: Running time is calculated as 1 + 4n + 1.
Time Complexity (Page 35)
Definition: Time complexity T_A(n) is the measure of running time of algorithm A on inputs of size n.
Types of Measures:
Worst-case (standard)
Average-case (sometimes)
Best-case (never)
Asymptotic Notation (Pages 39-43)
Ignoring Machine Dependent Constants:
Use of e-notation and O-notation.
O-notation: A function f is O(g) if there exists a constant C > 0 such that f(n) ≤ Cf(n) for sufficiently large n.
Interpretation: f grows no faster than g.
Θ-notation: A function f is Θ(g) if there exist constants C1, C2 > 0 such that C1g(n) ≤ f(n) ≤ C2g(n).
Example: Finding m in Array (Page 44)
Input: X = [2, 3, 1, 4, 2], m = 4
Running time: 1 + 4n + 1 = O(n).
Input Size and Complexity (Pages 45-46)
Input Size Definition: Amount of memory occupied by input with reasonable encoding.
Example: 13 = (1101) is reasonable; 13 = (1111111111111) is unreasonable.
Common Time Complexities:
O(1): constant-time algorithm
O(n): linear
O(n^k): polynomial
O(k^n): exponential
Comparisons of complexities: O(n log n) < O(n^2) < O(n^3)
Importance of Algorithm Efficiency (Page 47-48)
Comparison of algorithm performance on different processor generations.
Example for 1 million inputs on Intel Pentium III vs. Intel Core i5.
Green Computing:
Emphasis on faster algorithms leading to fewer computations and reduced energy consumption.