Lecture Notes on Algorithm Complexity

Introduction to Algorithm Complexity

• Focus on understanding time complexity and space complexity of different algorithms.
• Use frequency count method to analyze the time taken by algorithms.

Finding the Sum of Elements in an Array

• Algorithm Description: Calculate the sum of all elements in an array of size 5.
• Time Complexity Analysis:
  • Each statement in the algorithm takes 1 unit of time.
  • The loop iterates for n + 1 times where n = 5.
  • Condition checks: 6 times total (5 times true, 1 time false).
  • Time function: F(n) = 2n + 1.
• Order of Growth: The degree of the polynomial is 1; hence the complexity is O(n).

Space Complexity

• Variables used: n, s (size of the array), etc.
• Space complexity: S(n) = n + 3; also considers constant factors.
• Order of Space Complexity: O(n).

Finding the Sum of Two Matrices

• Algorithm Description: Sum of two n x n matrices.
• Time Complexity Analysis:
  • Each loop executes for n + 1 times.
  • Inner loop executes for n times resulting in time function: F(n) = n^2 + n.
• Order of Growth: Degree is 2; thus, complexity is O(n^2).

Space Complexity for Matrices

• Variables used include matrices A, B, C and scalars i, j.
• Space complexity: S(n) = 3n^2 + 3.
• Order of Space Complexity: O(n^2).

Multiplication of Two Matrices

• Algorithm Overview: Involves three nested loops.
• Time Complexity Analysis:
  • Each loop executes for n + 1 times.
  • Total execution: 4n^3 times.
  • Time function: F(n) = 3n^3 + (2n + 1).
• Order of Growth: Degree is 3; hence complexity is O(n^3).

Space Complexity for Multiplication of Matrices

• Variables used include matrices A, B, C and scalars i, j, k.
• Space complexity: S(n) = 3n^2 + 4.
• Order of Space Complexity: O(n^2).

Summary of Algorithm Complexities Examined

• Finding Sum of Array: Time - O(n), Space - O(n).
• Sum of Two Matrices: Time - O(n^2), Space - O(n^2).
• Multiplication of Two Matrices: Time - O(n^3), Space - O(n^2).

Conclusion

• Understanding the time and space complexities is crucial for analyzing algorithms.
• The next lecture will cover additional algorithms and their analysis methods.