Analysis of Algorithms

Chapter Scope

• Efficiency Goals: The chapter will discuss efficiency goals in the context of algorithm analysis.
• Algorithm Analysis: An introduction to the concept of algorithm analysis.
• Big-Oh Notation: Explanation and use of Big-Oh notation for expressing algorithm complexity.
• Asymptotic Complexity: Introduce the concept of asymptotic complexity.
• Comparing Growth Functions: The chapter will compare various growth functions.

Algorithm Efficiency

• The efficiency of an algorithm is generally expressed in terms of CPU time.
• The analysis of algorithms categorizes algorithms by efficiency.
• Dishwashing Example: Washing a dish takes 30 seconds, drying takes 30 seconds.
  • Washing and drying n dishes takes n minutes. This implies a linear relationship between the number of dishes and the time required.
• A less efficient approach involves redrying all previously washed dishes after washing another one.

Problem Size

• For algorithm analysis, define the problem size.
• Dishwashing: Size n = number of dishes.
• Search Algorithm: Size = size of the search pool.
• Sorting Algorithm: Size = number of elements to be sorted.

Growth Functions

• Optimize for time complexity (CPU time) or space complexity (memory space).
• CPU time is generally the focus.
• A growth function shows the relationship between the problem size n and the optimized value (time).

Asymptotic Complexity

• The growth function of the second dishwashing algorithm is t(n) = 15n^2 + 45n.
• Knowing the exact growth function is often unnecessary.
• Asymptotic complexity is the general nature of the algorithm as n increases.

Asymptotic Complexity

• Asymptotic complexity is based on the dominant term of the growth function, which increases most quickly as n increases.
• For the second dishwashing algorithm, the dominant term is n^2.

Big-Oh Notation

• Coefficients and lower order terms become less relevant as n increases.
• An algorithm is order n^2, written as O(n^2).
• This is Big-Oh notation.
• Big-Oh categories exist like O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), O(n!).
• Algorithms in the same category have similar efficiency, but may not have equal growth functions or behave identically for all n.

Comparing Growth Functions

• Faster processors do not diminish the importance of efficient algorithms.
• A faster CPU helps, but does not change the dominant term.

Comparing Growth Functions

• As n increases, growth functions diverge dramatically.

Comparing Growth Functions

• For large values of n, the difference is even more pronounced.

Analyzing Loop Execution

• Determine the order of the loop body, then multiply by the number of executions.

• Example:

  for (int count = 0; count < n; count++)
      // some sequence of O(1) steps
  

  • n loop executions * O(1) operations = O(n) efficiency.

Analyzing Loop Execution

• Consider the following loop:

  count = 1;
  while (count < n) {
      count *= 2;
      // some sequence of O(1) steps
  }
  

  • The loop is executed log_2{n} times, resulting in O(log n) complexity.

Analyzing Nested Loops

• For nested loops, multiply the complexity of the outer loop by the complexity of the inner loop.

• Example:

  for (int count = 0; count < n; count++)
      for (int count2 = 0; count2 < n; count2++) {
          // some sequence of O(1) steps
  }
  

  • Both inner and outer loops have complexity O(n).
  • The overall efficiency is O(n^2).

Analyzing Method Calls

• The body of a loop may contain a method call.
• To determine the order of the loop body, the order of the method must be taken into account.
• The overhead of the method call itself is generally ignored.