Page 25 - Data Structures Interactive Book

time ( ), logarithmic time ( ⁡ ), linear time ( ), and quadratic time ( ), Big-O
provides a universal language for comparing efficiency.

2.2.1 Common Growth Rates

• Constant time ( ): Execution time does not depend on input size. Example:
accessing an element in an array by index.

• Logarithmic time ( ⁡ ): Performance grows slowly as input increases.
Example: binary search.
• Linear time ( ): Execution time grows proportionally with input size. Example:
linear search.

• Quadratic time ( ): Performance grows rapidly, often seen in nested loops.
Example: bubble sort.

2.2.2 Examples in C++

Consider searching for an element in an array:

These examples highlight how algorithm choice directly affects efficiency.

2.3 Best, Worst, and Average Case Analysis

Algorithm performance can vary depending on the input. To capture this variability,

we analyze algorithms in terms of best case, worst case, and average case scenarios.

2.3.1 Best Case

The best case represents the scenario where the algorithm performs the minimum

25