Runtime Analysis

From Dr. Pitmann's Lecture Slides

Why does Big O Notation focus on worst case running time

It provides an upper bound on runtime, which is critical in time-sensitive or safety-critical applications. Worst-case guarantees the algorithm will never perform slower than the bound

What does Big O Measure?

It measures the asymptotic growth rate of an algorithm’s running time as the input size becomes very large

What is the meaning of O(n)

Linear time - the runtime grows proportionally with the input size.

What is the meaning of O(log n)

Logarithmic time - the runtime grows slowly, often due to repeatedly halving the input (binary search)

What is the meaning of O(n log n)

Linearithmic time - common in efficient sorting algorithms like mergesort and heapsort

What is the meaning of O(n²)

Quadratic time - often arises from nested loops where each loop runs n times

How do nested loops affect runtime?

Two simple nested loops over the same n elements result in O(n²) work, since the inner loop runs for each iteration of the outer loop

What is the meaning of O(1)

Constant time - the quickest, when you need to find an element in a HashMap