Analysis of Algorithms: Best, Worst, and Average Cases

Overview

• Discussed best, worst, and average case analysis for algorithms using examples of linear search and binary search tree (BST).
• Key concepts: best case, worst case, average case time complexities.
• Introduced asymptotic notations: Big O, Big Omega, and Theta.

Linear Search

Method

• Searches for an element by scanning each element of the list from left to right.

Best Case

• Condition: Searching for an element at the first index.
• Time Complexity: Constant time (O(1)).

Worst Case

• Condition: Searching for an element at the last index or not present in the list.
• Time Complexity: Linear time (O(n)).

Average Case

• Condition: Calculated by considering all possible cases (element found at any index).
• Formula: ((n+1)/2).
• Time Complexity: Linear time (\Theta(n)).

Summary

• Best Case: (O(1))
• Worst Case: (O(n))
• Average Case: (\Theta(n))

Asymptotic Notations

• Best case: (T(n) = 1 \Rightarrow O(1), \Omega(1), \Theta(1)).
• Worst case: (T(n) = n \Rightarrow O(n), \Omega(n), \Theta(n)).
• Average case: (T(n) = (n+1)/2 \Rightarrow O(n), \Omega(n), \Theta(n)).

Binary Search Tree (BST)

Method

• BST properties: left child node < parent node < right child node.
• Efficient for searching if tree is balanced.

Best Case

• Condition: Searching for the root element.
• Time Complexity: Constant time (O(1)).

Worst Case

• Condition: Searching for a leaf element.
• Time Complexity: Dependent on the height of the tree.
  • Balanced tree height: (\log n)
  • Skewed tree height: (n)

Average Case

• Generally dependent on the height, resembles worst case due to complexity.
• Time Complexity: (\Theta(\log n)) for balanced trees, (\Theta(n)) for skewed trees.

Types of Trees

• Balanced BST: Minimum height
  • Time Complexity: (\log n)
• Skewed BST: Maximum height
  • Time Complexity: (n)
• Worst case minimum time: (O(\log n))
• Worst case maximum time: (O(n))

Asymptotic Notations

• Best case: (T(n) = 1 \Rightarrow O(1), \Omega(1), \Theta(1)).
• Worst case: (T(n) = \log n \Rightarrow O(\log n), \Omega(\log n), \Theta(\log n)) for balanced tree.
• Worst case: (T(n) = n \Rightarrow O(n), \Omega(n), \Theta(n)) for skewed tree.

Key Takeaways

• Analysis involves understanding best, worst, and average case time complexities.
• Asymptotic notations are used to describe time complexities for different cases.
• Linear search is simple but can be inefficient for large data sets.
• Binary search tree efficiency heavily depends on its structure; balanced trees offer logarithmic time complexity, while skewed trees degrade to linear time complexity.

Final Notes

• Understanding best, worst, and average case helps in selecting appropriate algorithms for different scenarios.
• Asymptotic notations provide a standardized way to express time complexities.