Describe the techniques of algorithm analysis

Time complexity measures how the execution time of an algorithm increases as the input size grows. We express this using Big O notation, which describes the upper bound (worst-case behavior) of an algorithm's running time.

The most common time complexity classes are:

• O(1) — Constant time: The algorithm takes the same amount of time regardless of input size. Example: accessing an element in an array by index.

• O(n) — Linear time: The execution time grows directly with the input size. Example: linear search, where we examine each element one by one.

• O(n²) — Quadratic time: Execution time grows proportionally to the square of the input size. Example: bubble sort and selection sort with nested loops.

• O(log n) — Logarithmic time: Execution time grows slowly; the input size is halved with each step. Example: binary search, where we divide the sorted list in half repeatedly.

• O(n log n) — Linearithmic time: Commonly seen in efficient sorting algorithms like merge sort and quick sort.

Worked Example: Analyzing Linear Search

Suppose we have an array of n student examination scores and we want to find whether a particular score exists using linear search:

for (i = 0; i < n; i++) {
    if (arr[i] == target)
        return i;
}

In the worst case, the target element is at the last position or does not exist at all. We would examine all n elements. Therefore, the time complexity is O(n). If the array has 100 student scores, in the worst case we check all 100; if it grows to 1000 scores, we might check all 1000.

Worked Example: Analyzing Binary Search

Binary search repeatedly divides a sorted array in half:

while (beg <= end) {
    mid = (beg + end) / 2;
    if (arr[mid] == target) return mid;
    else if (target < arr[mid]) end = mid - 1;
    else beg = mid + 1;
}

Each comparison eliminates half of the remaining elements. With n elements, we can divide in half at most log₂(n) times. Thus, the time complexity is O(log n). For n = 1024, we need only about 10 comparisons instead of 1024.

Space complexity measures the amount of memory an algorithm needs to execute. This includes memory for input data, temporary variables, and recursion stack space.

• O(1) — Constant space: The algorithm uses a fixed amount of memory regardless of input size. Example: searching in an array without creating additional data structures.

• O(n) — Linear space: Memory usage grows with input size. Example: creating a new array to store sorted results.

When analyzing algorithms, we consider both time and space. An algorithm that runs quickly but uses excessive memory may not be suitable for systems with limited resources, such as mobile applications or embedded systems.

Algorithms can perform differently depending on the specific input data. We analyze three scenarios:

• Best case: The most favorable input where the algorithm performs optimally. For linear search, best case is O(1) when the target is the first element.

• Worst case: The least favorable input where the algorithm takes the longest. For linear search, worst case is O(n) when the target is last or absent.

• Average case: The expected performance over all possible inputs, often approximated mathematically.

When comparing algorithms, programmers typically focus on worst-case complexity because it guarantees performance under any circumstances.

Beyond Big O, two other notations are commonly used:

• Big Omega (Ω): Describes the lower bound—best possible running time. Binary search is Ω(1) when the target is found immediately.

• Big Theta (Θ): Describes when upper and lower bounds are the same—tight bound on running time. An algorithm that always takes exactly n steps has Θ(n).

For most practical purposes at this level, Big O notation suffices for comparing algorithm efficiency.

In Tanzanian markets, traders often organize their stock lists to find items quickly. A shopkeeper in Buguruni keeping a notebook of 500 items would benefit from understanding algorithm analysis: using a sorted list with binary search means finding any item in about 9 steps instead of potentially 500 steps, saving significant time during busy market hours when customers expect quick service.