1.
Significance of Big-O Notation:
● Big-O notation provides a way to express the upper bound or worst-case scenario of an
algorithm's time or space complexity.
● It helps in comparing and analyzing algorithms independently of hardware, programming
language, or constant factors.
2. Asymptotic Complexity:
● Asymptotic complexity measures the growth rate of an algorithm's resource usage (time
or space) as the input size approaches infinity.
● It focuses on the dominant term with the highest impact on complexity, ignoring lower-
order terms and constants.
3. Rule of Sums and Rule of Products
● Rule of Sums: Used when the algorithm's steps can be executed in either/or fashion.
The complexity is the sum of the complexities of each alternative.
● Rule of Products: Applied when the algorithm's steps involve a sequence of tasks
executed in a nested or sequential manner. The complexity is the product of the
complexities of each step.
4. Recursion in Problem Solving
● Recursion involves solving a problem by breaking it down into smaller instances of the
same problem.
● Examples of recursive algorithms include factorial calculation, Fibonacci sequence
generation, and binary tree traversal.
5. Common Data Structures and Big-O Analysis
● Arrays: Access and search in O(1), insertion and deletion in O(n) in the worst case.
● Linked Lists: Search in O(n), insertion and deletion in O(1) if the node is given.
● Stacks and Queues: Operations generally in O(1).
● Trees (Binary Search Trees): Search, insertion, and deletion in O(log n) on average.
● Hash Tables: Search, insertion, and deletion in O(1) on average (amortized).