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:

  1. Function calls

  2. Logical operations (AND, OR, comparison)

  3. Arithmetic operations (+, -, *, /)

  4. Assignment operations (e.g., x = 5)

  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:

    1. 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:

    1. 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.