Analysing Algorithms
Definition:
Analysing algorithms involves determining their efficiency and resource usage
(like time and space) as a function of the input size. It helps evaluate the
performance of an algorithm and choose the most optimal solution for a given
problem.
Key Concepts:
1. Correctness: Verifying that the algorithm produces the expected output for
all valid inputs.
2. Efficiency:
o Time Complexity: Measures how the running time of the algorithm
grows with the size of the input.
o Space Complexity: Measures the amount of memory the algorithm
requires.
3. Scalability: Examines how well the algorithm performs as input size
increases.
4. Asymptotic Analysis:
o Focuses on the growth of the algorithm's resource usage for large
input sizes.
o Includes Big-O, Theta (Θ), and Omega (Ω) notations.
5. Input Size:
o Denoted as n, it represents the number of elements or the magnitude
of the input to the algorithm.
6. Worst, Best, and Average Case:
o Worst-case: Maximum time the algorithm can take for any input.
o Best-case: Minimum time for the most favourable input.
o Average-case: Expected time for a random input.
Importance:
• Helps predict algorithm performance.
• Guides the selection of the most appropriate algorithm for real-world
applications.
• Identifies bottlenecks and areas for optimization.
