Java: Chapter 5 – Algorithm Analysis and Big-O Notation

What is the focus of Chapter 5?

Understanding how to analyze and compare the performance of algorithms using Big-O notation and asymptotic analysis.

What is algorithm analysis?

The study of how an algorithm’s resource usage (time and memory) grows as input size increases.

What is time complexity?

A measure of the number of basic operations an algorithm performs as a function of input size n.

What is space complexity?

A measure of the amount of memory an algorithm uses relative to input size n.

Why is algorithm analysis important?

It allows us to predict performance, compare algorithms, and select the most efficient for large data sets.

What is Big-O notation used for?

To describe the upper bound of an algorithm’s growth rate — its worst-case running time.

What does O(f(n)) represent?

An asymptotic upper bound: the algorithm’s runtime grows no faster than a constant multiple of f(n).

Give an example of constant time complexity.

O(1) — the algorithm runs in the same amount of time regardless of input size.

Give an example of linear time complexity.

O(n) — runtime grows proportionally to input size.

Give an example of quadratic time complexity.

O(n²) — runtime grows with the square of the input size, common in nested loops.

What is logarithmic time complexity?

O(log n) — growth rate decreases as input increases; typical for binary search.

What is exponential time complexity?

O(2ⁿ) — runtime doubles for every new input element, often infeasible for large n.

What is the difference between Big-O, Big-Ω, and Big-Θ?

Big-O gives an upper bound; Big-Ω gives a lower bound; Big-Θ defines tight bounds (both upper and lower).

How do you define f(n) ∈ Θ(g(n))?

If constants c₁, c₂, m exist such that c₁g(n) < f(n) < c₂g(n) for all n > m.

What does asymptotic analysis mean?

It studies an algorithm’s behavior as input size n approaches infinity, ignoring constants and small inputs.

Why does asymptotic analysis ignore constant factors?

Because they have little effect on growth rate for large n.

What are some limitations of Big-O analysis?

It ignores constants, system factors, caching effects, and average-case differences.

What is the difference between worst-case and average-case analysis?

Worst-case assumes the least favorable input; average-case considers expected input distribution.

What is the best-case analysis?

The minimum possible running time under ideal input conditions.

What is binary search’s time complexity?

O(log n) — because it halves the search space with each iteration.

What is linear search’s time complexity?

O(n) — it checks each element until it finds the target or reaches the end.

Why is binary search more efficient than linear search?

It reduces the number of comparisons by dividing the search interval in half each time.

What is the purpose of using System.nanoTime or System.currentTimeMillis in Java?

To measure actual execution time experimentally for empirical algorithm analysis.

What are asymptotic classes ordered from fastest to slowest?

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).

What does it mean if one algorithm is O(n) and another is O(n²)?

The O(n) algorithm will eventually outperform the O(n²) algorithm as n grows large.

What is the role of Big-O in software engineering?

It provides a language to compare algorithms’ scalability independent of hardware or language.

Why might a slower asymptotic algorithm be preferable?

It may be simpler, more maintainable, or faster for small input sizes due to lower constants.

How does system design affect algorithm performance?

Memory hierarchy, caching, and CPU architecture can influence real-world speed beyond Big-O predictions.

What is the project or exercise theme of Chapter 5?

Applying algorithm analysis concepts through practical examples such as binary search and timing comparisons.