Algorithm Analysis

Think of cooking food. Time efficiency is like how many minutes the cooking takes. Space efficiency is like how many extra vessels and counter space we need while cooking, apart from the raw ingredients and the final dish.

Sweeping a small room takes less time. Sweeping a big hall takes more time. Here, the size of the room is like input size $n$, and the sweeping time grows as the room size grows.

Suppose we want to check if a student ID is present in a record file. The algorithm reads each record one by one, compares the ID, and stops when found or when the file ends. If the file has $n$ records, the algorithm may check up to $n$ records in the worst case. If the file size doubles, the work also doubles. So here, input size is the number of records.

For a matrix, we can measure size as the number of rows, or as the total number of elements (rows times columns). Both are valid, but the growth function looks different depending on which one we use.

An algorithm that checks spelling works on each character of a word, so its input size is the number of characters. An algorithm that counts how many words are in a sentence works on each word, so its input size is the number of words.

If two cooks use the same recipe, but one has a fast gas stove and the other has a slow stove, their cooking time will differ. But the recipe, that is the method, is the same for both. So, we should judge the recipe by its steps, not by the stove used.

Suppose we want to check if a registration number is present in a list of employee records. The algorithm compares the target number with each record one by one, and stops when it matches or the list ends. Here, the basic operation is the comparison between two numbers. If the list has $n$ records, the algorithm does at most $n$ comparisons.

If checking one record takes $c_{op}$ time, and we have $n$ records, then in the worst case, the total time is approximately $c_{op} \cdot n$. If $n$ becomes double, the total time also becomes roughly double.

If an algorithm takes $5n$ steps and another takes $2n$ steps, both grow in the same straight line pattern as $n$ increases. So, we say both algorithms have the same growth pattern, and we ignore the constants $5$ and $2$ while comparing their efficiency.

For a short distance, walking and running may take almost the same time. But for a very long road, running clearly takes much less time than walking. In the same way, for small input, slow and fast algorithms look similar, but for large input, the difference becomes clear.

Suppose an algorithm needs $f(n) = n^2$ operations. If input size becomes double, from $n$ to $2n$, then \[ f(2n) = (2n)^2 = 4n^2 \] So the work becomes four times more.

Now suppose another algorithm needs $g(n) = n$ operations. If input size becomes double, then \[ g(2n) = 2n \] So the work becomes only double.

This shows that even if both algorithms look similar for small input, the algorithm with $n^2$ becomes much costlier than the algorithm with $n$, as input size grows large.

Arrange the following functions in increasing order of growth: \[ n,    \log n,    n^2,    1 \] Order: $1 < \log n < n < n^2$

Arrange the following functions in increasing order of growth: \[ n!,    2^n,    n^3,    n \log n \] Order: $n \log n < n^3 < 2^n < n!$

Arrange the following functions in increasing order of growth: \[ \sqrt{n},    n,    \log n,    n^2 \log n \] Order: $\log n < \sqrt{n} < n < n^2 \log n$

Arrange the following functions in increasing order of growth: \[ 2^n,    n^{10},    10^n,    \log_2 n \] Order: $\log_2 n < n^{10} < 2^n < 10^n$

Arrange the following functions in increasing order of growth: \[ n \log n,    n^2,    n,    2^{\log n} \] Hint: simplify $2^{\log n}$ first using log identity, base 2.

Order: $n = 2^{\log n} < n \log n < n^2$

If we buy 2 apples, paying 5 rupees extra for a bag does matter. But if we buy 1000 apples, that same 5 rupees extra does not matter much. In the same way, small constants in running time do not matter when input size is very large.

Suppose Algorithm A takes $5n + 20$ steps, and Algorithm B takes $n^2 + 3n$ steps. Algorithm A grows linearly, and Algorithm B grows quadratically. For small $n$, both may take similar steps. But for large $n$, Algorithm A becomes much faster than Algorithm B, because linear growth is slower than quadratic growth.

Suppose Algorithm A needs $4n + 10$ operations, and Algorithm B needs $n^2$ operations.

Case 1: Small input, $n = 5$ \[ A = 4(5) + 10 = 30,      B = 5^2 = 25 \] Here, B is actually doing fewer operations than A.

Case 2: Large input, $n = 1000$ \[ A = 4(1000) + 10 = 4010,      B = 1000^2 = 1{,}000{,}000 \] Now, A is doing far fewer operations than B.

This shows that for small input, the algorithm with a worse order of growth can still look better. But as input size grows large, the algorithm with the better order of growth always wins. So, asymptotically, Algorithm A is the better choice.

For each running time expression, identify the dominant term, that means the order of growth.

1. $T(n) = 7n^3 + 50n^2 + 100$    $\rightarrow$ dominant term is $n^3$

2. $T(n) = 2^n + n^{10}$    $\rightarrow$ dominant term is $2^n$

3. $T(n) = 20n \log n + 5n$    $\rightarrow$ dominant term is $n \log n$

4. $T(n) = n! + 2^n + n^5$    $\rightarrow$ dominant term is $n!$

Think of a speed limit board on a highway that says maximum speed is 80. A car may go slow sometimes, fast sometimes, but it never crosses 80, once it is on the highway. Big-Oh is similar, $c \cdot g(n)$ acts like a speed limit, and $f(n)$ never crosses it, after point $n_0$.

We want to show $f(n) = O(n)$.

We need to find $c > 0$ and $n_0$ such that \[ 0 \le 3n + 8 \le c \cdot n    \text{for all } n \ge n_0 \]

For $n \ge 8$, we know $8 \le n$. So, \[ 3n + 8 \le 3n + n = 4n \]

This means $3n + 8 \le 4n$ for all $n \ge 8$.

Choosing $c = 4$ and $n_0 = 8$, the condition holds. So, \[ 3n + 8 = O(n) \]

We want to show $f(n) = O(n^2)$.

We need $c > 0$ and $n_0$ such that \[ 0 \le n^2 + 1 \le c \cdot n^2    \text{for all } n \ge n_0 \]

For $n \ge 1$, we know $1 \le n^2$. So, \[ n^2 + 1 \le n^2 + n^2 = 2n^2 \]

This means $n^2 + 1 \le 2n^2$ for all $n \ge 1$.

Choosing $c = 2$ and $n_0 = 1$, the condition holds. So, \[ n^2 + 1 = O(n^2) \]

We want to show $f(n) = O(n^2)$.

For $n \ge 5$, we know $5 \le n$. So, \[ 100n + 5 \le 100n + n = 101n \]

Also, for $n \ge 1$, we know $n \le n^2$, so $101n \le 101n^2$.

Combining, for $n \ge 5$, \[ 100n + 5 \le 101n^2 \]

Choosing $c = 101$ and $n_0 = 5$, the condition holds. So, \[ 100n + 5 = O(n^2) \]

Prove that $f(n) = O(n^2)$.

Solution: For $n \ge 1$, we know $3n \le 3n^2$. So, \[ 5n^2 + 3n \le 5n^2 + 3n^2 = 8n^2 \] Choosing $c = 8$ and $n_0 = 1$, we get $5n^2 + 3n = O(n^2)$.

Prove that $f(n) = O(n^3)$.

Solution: For $n \ge 50$, we know $50n^2 \le n \cdot n^2 = n^3$. So, \[ n^3 + 50n^2 \le n^3 + n^3 = 2n^3 \] Choosing $c = 2$ and $n_0 = 50$, we get $n^3 + 50n^2 = O(n^3)$.

Prove that $f(n) = O(1)$.

Solution: Here $f(n) = 7$ stays fixed, it does not grow with $n$. So, \[ 7 \le 7 \cdot 1 \] Choosing $c = 7$ and $n_0 = 1$, we get $7 = O(1)$. This shows constant functions are written as $O(1)$.

Prove that $f(n) = O(n \log n)$.

Solution: For $n \ge 2$, we know $\log n \ge 1$, so $n \le n \log n$. So, \[ n \log n + n \le n \log n + n \log n = 2 n \log n \] Choosing $c = 2$ and $n_0 = 2$, we get $n \log n + n = O(n \log n)$.

Prove that $f(n) = O(n^2)$.

Solution: For $n \ge 2$, we know $\log n \le n$, so $3n \log n \le 3n^2$. Also for $n \ge 1$, $10 \le 10n^2$. So, \[ 2n^2 + 3n \log n + 10 \le 2n^2 + 3n^2 + 10n^2 = 15n^2 \] Choosing $c = 15$ and $n_0 = 2$, we get $2n^2 + 3n \log n + 10 = O(n^2)$.

Think of a rule that says a worker must be paid at least 500 rupees per day. The actual pay can be more, some days much more, but it never falls below this floor amount. Big-Omega is similar, $c \cdot g(n)$ acts like a floor, and $f(n)$ never falls below it, after point $n_0$.

We want to show $f(n) = \Omega(n^2)$.

We need $c > 0$ and $n_0$ such that \[ 0 \le c \cdot n^2 \le 3n^2 + 2n    \text{for all } n \ge n_0 \]

Since $2n \ge 0$ for all $n \ge 0$, \[ 3n^2 + 2n \ge 3n^2 \]

This means $3n^2 + 2n \ge 3n^2$ for all $n \ge 0$.

Choosing $c = 3$ and $n_0 = 1$, the condition holds. So, \[ 3n^2 + 2n = \Omega(n^2) \]

Prove that $f(n) = \Omega(n^2)$.

Solution: For $n \ge 6$, we know $3n \le \dfrac{1}{2}n^2$. So, \[ n^2 - 3n \ge n^2 - \frac{1}{2}n^2 = \frac{1}{2}n^2 \] Choosing $c = \dfrac{1}{2}$ and $n_0 = 6$, we get $n^2 - 3n = \Omega(n^2)$.

Prove that $f(n) = \Omega(n)$.

Solution: Since $2 \ge 0$ for all $n$, \[ 7n + 2 \ge 7n \] Choosing $c = 7$ and $n_0 = 1$, we get $7n + 2 = \Omega(n)$.

Prove that $f(n) = \Omega(n^3)$.

Solution: Since $4n \ge 0$ for all $n \ge 0$, \[ n^3 + 4n \ge n^3 \] Choosing $c = 1$ and $n_0 = 1$, we get $n^3 + 4n = \Omega(n^3)$.

Prove that $f(n) = \Omega(n)$.

Solution: For $n \ge 2$, we know $\log n \ge 1$. So, \[ n \log n \ge n \cdot 1 = n \] Choosing $c = 1$ and $n_0 = 2$, we get $n \log n = \Omega(n)$.

Prove that $f(n) = \Omega(n^2)$.

Solution: It is known that $2^n$ grows much faster than any polynomial like $n^2$, for large $n$. We can check small values to find a safe starting point. At $n = 6$, $2^n = 64$ and $n^2 = 36$, so $2^n \ge n^2$ here. As $n$ increases further, $2^n$ grows much faster than $n^2$, so the inequality keeps holding. \[ 2^n \ge n^2    \text{for all } n \ge 6 \] Choosing $c = 1$ and $n_0 = 6$, we get $2^n = \Omega(n^2)$.

Think of a narrow road with a wall on the left side and a wall on the right side. A car driving on this road can never go beyond the left wall, and can never go beyond the right wall, it always stays between them. Big-Theta is similar, $f(n)$ always stays between the lower wall $c_1 \cdot g(n)$ and the upper wall $c_2 \cdot g(n)$.

We want to show $f(n) = \Theta(n^2)$.

Step 1: Upper Bound. For $n \ge 1$, we know $3n \le 3n^2$ and $4 \le 4n^2$. So, \[ f(n) \le 2n^2 + 3n^2 + 4n^2 = 9n^2 \] This gives us $c_2 = 9$.

Step 2: Lower Bound. Since all terms in $f(n)$ are non-negative for $n \ge 1$, \[ f(n) \ge 2n^2 \] This gives us $c_1 = 2$.

Step 3: Combine. For all $n \ge 1$, \[ 2n^2 \le 2n^2 + 3n + 4 \le 9n^2 \]

Choosing $c_1 = 2$, $c_2 = 9$, and $n_0 = 1$, both conditions hold together. So, \[ 2n^2 + 3n + 4 = \Theta(n^2) \]

Prove that $f(n) = \Theta(n)$.

Upper bound: For $n \ge 1$, $5n + 2 \le 5n + 2n = 7n$, so $c_2 = 7$.

Lower bound: Since $2 \ge 0$, $5n + 2 \ge 5n$, so $c_1 = 5$.

Choosing $c_1 = 5$, $c_2 = 7$, $n_0 = 1$, we get $5n + 2 = \Theta(n)$.

Prove that $f(n) = \Theta(n^2)$.

Upper bound: For $n \ge 1$, $n \le n^2$, so $n^2 + n \le n^2 + n^2 = 2n^2$, giving $c_2 = 2$.

Lower bound: Since $n \ge 0$, $n^2 + n \ge n^2$, giving $c_1 = 1$.

Choosing $c_1 = 1$, $c_2 = 2$, $n_0 = 1$, we get $n^2 + n = \Theta(n^2)$.

Prove that $f(n) = \Theta(n^3)$.

Upper bound: For $n \ge 1$, $2n^2 \le 2n^3$ and $n \le n^3$, so \[ f(n) \le 3n^3 + 2n^3 + n^3 = 6n^3,    c_2 = 6 \]

Lower bound: Since all terms are non-negative, $f(n) \ge 3n^3$, so $c_1 = 3$.

Choosing $c_1 = 3$, $c_2 = 6$, $n_0 = 1$, we get $3n^3 + 2n^2 + n = \Theta(n^3)$.

Prove that $f(n) = \Theta(n^2)$.

Lower bound: For $n \ge 12$, $3n \le \dfrac{1}{4}n^2$, so \[ f(n) \ge \frac{1}{2}n^2 - \frac{1}{4}n^2 = \frac{1}{4}n^2,    c_1 = \frac{1}{4} \]

Upper bound: Since $3n \ge 0$ does not add value here, simply $f(n) \le \dfrac{1}{2}n^2$, so $c_2 = \dfrac{1}{2}$.

Choosing $c_1 = \dfrac{1}{4}$, $c_2 = \dfrac{1}{2}$, $n_0 = 12$, we get $\dfrac{1}{2}n^2 - 3n = \Theta(n^2)$.

Prove that $f(n) = \Theta(n \log n)$.

Upper bound: For $n \ge 2$, $\log n \ge 1$, so $n \le n \log n$, giving \[ f(n) \le n \log n + n \log n = 2n \log n,    c_2 = 2 \]

Lower bound: Since $n \ge 0$, $f(n) \ge n \log n$, giving $c_1 = 1$.

Choosing $c_1 = 1$, $c_2 = 2$, $n_0 = 2$, we get $n \log n + n = \Theta(n \log n)$.

If Ravi is as tall as Suresh, and Suresh is as tall as Mahesh, then Ravi is also as tall as Mahesh. Transitivity in notations works the same way, just with growth rate instead of height.

Think back to the road between two walls example used for Big-Theta. The left wall is the lower bound, which is Big-Omega. The right wall is the upper bound, which is Big-Oh. If we show the car never crosses the left wall, and never crosses the right wall, we have shown the car always stays on this road, which is exactly Big-Theta.

We want to show that for $a > 0$, $f(n) = an^2 + bn + c = \Theta(n^2)$.

Step 1: Prove Big-Oh. For $n \ge 1$, we know $|bn| \le |b| n^2$ and $|c| \le |c| n^2$. So, \[ f(n) \le an^2 + |b|n^2 + |c|n^2 = (a + |b| + |c|) n^2 \] This shows $f(n) = O(n^2)$.

Step 2: Prove Big-Omega. Since $a > 0$, the term $an^2$ is the strongest term, and it grows faster than $bn$ and $c$. So, for large enough $n$, the smaller terms cannot pull the value below half of $an^2$. There exists some $n_0$ such that \[ an^2 + bn + c \ge \frac{a}{2} n^2    \text{for all } n \ge n_0 \] This shows $f(n) = \Omega(n^2)$.

Step 3: Combine. Since $f(n)$ is both $O(n^2)$ and $\Omega(n^2)$, by the rule connecting the three notations, \[ an^2 + bn + c = \Theta(n^2) \]

Given $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$, with $h(n) = n^2$, show $f(n) = \Theta(h(n))$.

Solution: Since $f(n) = \Theta(g(n))$, and $g(n) = \Theta(h(n))$ (because both $g(n)$ and $h(n)$ are $\Theta(n^2)$), by transitivity, $f(n) = \Theta(h(n))$.

Given $n = O(n^2)$, what can we say about $n^2$ using transpose symmetry?

Solution: By transpose symmetry, since $n = O(n^2)$, it directly follows that $n^2 = \Omega(n)$.

Show that $f(n) = 4n^2 - 5n$ is $\Theta(n^2)$.

Upper bound: For $n \ge 1$, $f(n) \le 4n^2$, so $f(n) = O(n^2)$.

Lower bound: For $n \ge 3$, $5n \le 2n^2$, so $f(n) \ge 4n^2 - 2n^2 = 2n^2$, giving $f(n) = \Omega(n^2)$.

Since both hold, $f(n) = \Theta(n^2)$.

If $5n^2 = \Theta(n^2)$, what can we say about $n^2$ in relation to $5n^2$?

Solution: By symmetry of Big-Theta, since $5n^2 = \Theta(n^2)$, it directly follows that $n^2 = \Theta(5n^2)$.

Given $n \log n = \Theta(n \log n)$, and $n \log n = \Theta(2n \log n)$, and $2n \log n = \Theta(3n \log n)$, what can we conclude about $n \log n$ and $3n \log n$?

Solution: Using transitivity twice, since $n \log n = \Theta(2n \log n)$ and $2n \log n = \Theta(3n \log n)$, we get $n \log n = \Theta(3n \log n)$.

Think of two brothers walking. Big-Oh is like saying the younger brother never walks faster than the older brother, but they could be walking at the exact same speed. Little-$o$ is like saying the younger brother always walks strictly slower, he can never catch up to the same speed, no matter how slow we let the older brother go.

We check whether $n = o(n^2)$, using the limit method. \[ \lim_{n \to \infty} \frac{n}{n^2} = \lim_{n \to \infty} \frac{1}{n} = 0 \] Since the limit is $0$, we conclude \[ n = o(n^2) \] This makes sense, because $n$ grows much slower than $n^2$, as $n$ becomes large.

We check whether $n^2 = o(n^2)$. \[ \lim_{n \to \infty} \frac{n^2}{n^2} = 1 \] Since the limit is $1$, not $0$, we conclude \[ n^2 \ne o(n^2) \] This confirms that little-$o$ does not allow same speed growth, only strictly slower growth is allowed.

Think of a runner who is always strictly faster than another runner, no matter how much we slow down the comparison runner. This is little-$\omega$, a strict, always faster relationship. Big-Omega only says our runner is never slower, they could even run at the same speed sometimes.

We check whether $n^2 = \omega(n)$, using the limit method. \[ \lim_{n \to \infty} \frac{n^2}{n} = \lim_{n \to \infty} n = \infty \] Since the limit is infinity, we conclude \[ n^2 = \omega(n) \] This makes sense, because $n^2$ grows much faster than $n$, as $n$ becomes large.

We check whether $2^n = \omega(n^{10})$. \[ \lim_{n \to \infty} \frac{2^n}{n^{10}} = \infty \] This is true because exponential growth always beats polynomial growth, eventually, no matter how large the power is. So, \[ 2^n = \omega(n^{10}) \]

Check whether $\log n = o(n)$.

Solution: \[ \lim_{n \to \infty} \frac{\log n}{n} = 0 \] Since the limit is $0$, we get $\log n = o(n)$.

Check whether $n^3 = o(n^2)$.

Solution: \[ \lim_{n \to \infty} \frac{n^3}{n^2} = \lim_{n \to \infty} n = \infty \] Since the limit is not $0$, we get $n^3 \ne o(n^2)$. In fact, $n^3 = \omega(n^2)$ instead.

Check whether $n! = \omega(2^n)$.

Solution: As $n$ becomes large, factorial growth becomes much faster than exponential growth. \[ \lim_{n \to \infty} \frac{n!}{2^n} = \infty \] So, $n! = \omega(2^n)$.

Check whether $5n^2 = o(n^2)$.

Solution: \[ \lim_{n \to \infty} \frac{5n^2}{n^2} = 5 \] Since the limit is a fixed constant, not $0$, we get $5n^2 \ne o(n^2)$. Instead, $5n^2 = \Theta(n^2)$.

Check whether $n \log n = \omega(n)$.

Solution: \[ \lim_{n \to \infty} \frac{n \log n}{n} = \lim_{n \to \infty} \log n = \infty \] Since the limit is infinity, we get $n \log n = \omega(n)$.

Think of two ways to compare numbers. We can say $a \le b$, which allows $a$ to be equal to $b$. Or we can say $a < b$, which does not allow them to be equal. Big-Oh is like $\le$, and little-$o$ is like $<$. The same pattern goes for Big-Omega and little-$\omega$.

Just like $f(n) = O(g(n))$ if and only if $g(n) = \Omega(f(n))$, the same flipping rule works for the strict family also. $f(n) = o(g(n))$ if and only if $g(n) = \omega(f(n))$. For example, since $n = o(n^2)$, by this flipping rule, we directly get $n^2 = \omega(n)$, without checking the limit again.

We already know from Practice 1 that $f(n) = O(n^3)$. Now check whether $f(n) = \Theta(n^3)$ is true. Since \[ \lim_{n \to \infty} \frac{n^2}{n^3} = 0 \ne \text{positive constant} \] $\Theta$ is ruled out. Since $O(g(n)) = o(g(n)) \cup \Theta(g(n))$, and $\Theta$ is ruled out, we directly conclude \[ f(n) = o(n^3) \] without needing to separately confirm the strict limit condition.

We know $\log n = o(n)$, and we know $n = o(n^2)$. By transitivity of $o$, without computing any new limit, we can directly conclude \[ \log n = o(n^2) \] By the transpose symmetry rule, this also tells us $n^2 = \omega(\log n)$.

\[ \lim_{n \to \infty} \frac{3n^2}{n^2} = 3 \] The limit is a positive constant, so $f(n) = \Theta(n^2)$. This also means $f(n) = O(n^2)$ and $f(n) = \Omega(n^2)$ are both true. But $f(n) \ne o(n^2)$ and $f(n) \ne \omega(n^2)$, since the limit is not $0$ and not $\infty$.

\[ \lim_{n \to \infty} \frac{n \log n}{n^2} = \lim_{n \to \infty} \frac{\log n}{n} = 0 \] The limit is $0$, so $f(n) = o(n^2)$. This also means $f(n) = O(n^2)$ is true. But $f(n) \ne \Theta(n^2)$, $f(n) \ne \Omega(n^2)$, and $f(n) \ne \omega(n^2)$.

Find the limit and classify the relationship.

Solution: \[ \lim_{n \to \infty} \frac{n^2}{n^3} = 0 \] So, $f(n) = o(n^3)$, which also means $f(n) = O(n^3)$.

Find the limit and classify the relationship.

Solution: \[ \lim_{n \to \infty} \frac{2^n}{3^n} = \lim_{n \to \infty} \left(\frac{2}{3}\right)^n = 0 \] So, $f(n) = o(3^n)$, which also means $f(n) = O(3^n)$.

Find the limit and classify the relationship.

Solution: Since $n^n$ multiplies $n$ copies of $n$, but $n!$ multiplies decreasing numbers below $n$, $n^n$ grows faster. \[ \lim_{n \to \infty} \frac{n!}{n^n} = 0 \] So, $f(n) = o(n^n)$, which also means $f(n) = O(n^n)$.

Find the limit and classify the relationship.

Solution: \[ \lim_{n \to \infty} \frac{7n^2 + 2n}{n^2} = 7 \] Since the limit is a positive constant, $f(n) = \Theta(n^2)$, which also means $f(n) = O(n^2)$ and $f(n) = \Omega(n^2)$.

Find the limit and classify the relationship.

Solution: \[ \lim_{n \to \infty} \frac{n^3}{n^2 \log n} = \lim_{n \to \infty} \frac{n}{\log n} = \infty \] So, $f(n) = \omega(n^2 \log n)$, which also means $f(n) = \Omega(n^2 \log n)$.

Here the two terms are $n^3$ and $n^2 \log n$. Since $n^3$ grows faster than $n^2 \log n$, the max rule tells us \[ n^3 + n^2 \log n = \Theta(n^3) \] We do not need to analyze both terms separately in later steps of an algorithm's analysis; only the dominant term $n^3$ matters for the overall growth rate.

Suppose an outer loop runs $\Theta(n)$ times, and for each outer iteration, an inner loop runs $\Theta(\log n)$ times. Treating these as $f_1(n) = \Theta(n)$ and $f_2(n) = \Theta(\log n)$, the product rule gives the total work as \[ f_1(n) \cdot f_2(n) = \Theta(n \log n) \] This is exactly why we multiply the bounds of nested loops instead of adding them.

Suppose an algorithm performs $5n^2 + 3n$ operations. Using the sum rule, this is $\Theta(n^2)$. Using the constant multiple property, we also see that a related algorithm performing $500n^2$ operations, or even $0.5n^2$ operations, is still $\Theta(n^2)$. Only the shape of growth matters, not the constant in front of it.

Given $f(n) = n \log n$ and $g(n) = n^2$, we already know $f(n) = O(n^2)$. Use the big-little split to decide whether $f(n) = o(n^2)$.

Solution: Check if $\Theta$ holds: \[ \lim_{n \to \infty} \frac{n \log n}{n^2} = 0 \ne \text{positive constant} \] $\Theta$ is ruled out, so since $O(g(n)) = o(g(n)) \cup \Theta(g(n))$, we conclude $f(n) = o(n^2)$.

Given $n^2 = \omega(n \log n)$ and $n \log n = \omega(n)$, what can we conclude?

Solution: By transitivity of $\omega$, \[ n^2 = \omega(n) \]

Classify $f(n) = 2^n + n^{100}$ using the max rule.

Solution: Since $2^n$ grows faster than any polynomial, including $n^{100}$, \[ 2^n + n^{100} = \Theta(2^n) \]

An algorithm has an outer loop of $\Theta(n^2)$ iterations, and inside each iteration it calls a subroutine that costs $\Theta(n)$. Find the total cost.

Solution: By the product rule, \[ \Theta(n^2) \cdot \Theta(n) = \Theta(n^3) \]

Consider a loop where, in the first round we do $1$ unit of work, in the second round $2$ units, in the third round $3$ units, and so on, till $n$ rounds. The total work is \[ 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2} \] which is $\Theta(n^2)$.

Consider a loop where, in round $i$, we do $i^2$ units of work, for $i = 1$ to $n$. The total work is \[ \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} \] which is $\Theta(n^3)$.

Consider a loop where, in round $i$, we do $2^i$ units of work, for $i = 0$ to $n$. The total work is \[ 1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1 \] which is $\Theta(2^n)$. This matches the idea that the last term in a growing geometric series dominates the entire sum.

Consider an algorithm where, in round $i$, the work depends on $\dfrac{n}{i}$, for $i = 1$ to $n$. The total work is \[ \sum_{i=1}^{n} \frac{n}{i} = n \sum_{i=1}^{n} \frac{1}{i} \approx n \ln n \] which is $\Theta(n \log n)$.

Consider a loop where, in round $i$, we do $\log i$ units of work, for $i = 1$ to $n$. The total work is \[ \sum_{i=1}^{n} \log i = \log(n!) = \Theta(n \log n) \]

Consider the sum $\sum_{i=1}^{n} (3i + 5)$. We split this into two parts. \[ \sum_{i=1}^{n} 3i + \sum_{i=1}^{n} 5 = 3 \cdot \frac{n(n+1)}{2} + 5n \] The dominant term here is $3 \cdot \dfrac{n(n+1)}{2}$, so the overall sum is $\Theta(n^2)$.

Find the order of growth of $\sum_{i=1}^{n} 4i$.

Solution: \[ \sum_{i=1}^{n} 4i = 4 \cdot \frac{n(n+1)}{2} = 2n(n+1) \] This is $\Theta(n^2)$.

Find the order of growth of $\sum_{i=1}^{n} 3i^2$.

Solution: \[ \sum_{i=1}^{n} 3i^2 = 3 \cdot \frac{n(n+1)(2n+1)}{6} = \frac{n(n+1)(2n+1)}{2} \] This is $\Theta(n^3)$.

Find the order of growth of $\sum_{i=0}^{n} 3^i$.

Solution: \[ \sum_{i=0}^{n} 3^i = \frac{3^{n+1} - 1}{3 - 1} \] This is $\Theta(3^n)$.

Find the order of growth of $\sum_{i=1}^{n} \left(i + \frac{1}{i}\right)$.

Solution: We split the sum into two parts. \[ \sum_{i=1}^{n} i + \sum_{i=1}^{n} \frac{1}{i} = \frac{n(n+1)}{2} + \ln n \] The term $\dfrac{n(n+1)}{2}$ dominates $\ln n$, so the overall sum is $\Theta(n^2)$.

Find the order of growth of $\sum_{i=1}^{n} \log(i^2)$.

Solution: Using log property, $\log(i^2) = 2 \log i$. \[ \sum_{i=1}^{n} 2 \log i = 2 \sum_{i=1}^{n} \log i = 2 \log(n!) \] This is $\Theta(n \log n)$.

Consider this code, which adds numbers from $1$ to $n$ into a variable sum.

sum = 0;
for (i = 1; i <= n; i++)
    sum = sum + i;

We now apply the general plan, one step at a time.

Step 1: Decide input size parameter. Here, the input is the number $n$ itself. So, our size parameter is simply $n$.

Step 2: Identify the basic operation. The line sum = sum + i; is inside the loop, and it is the operation that repeats. This addition is our basic operation.

Step 3: Check dependency on input configuration. The loop always runs from $i = 1$ to $i = n$, no matter what value $n$ has, there is no condition like searching for a target, where the count could change based on where something is found. So, here, the count depends only on $n$, we do not need separate best case, worst case, average case, the count is fixed for a given $n$.

Step 4: Set up the summation. The basic operation runs once for every value of $i$ from $1$ to $n$. So the count is \[ C(n) = \sum_{i=1}^{n} 1 \]

Step 5: Solve the summation. Adding $1$, exactly $n$ times, gives \[ C(n) = n \] So, the running time is $\Theta(n)$.

The running time of a loop is exactly proportional to the running time of the statements inside the loop, multiplied by the number of times the loop runs.

for (i = 1; i <= n; i++)
    m = m + 2;   // constant time

Here, the loop runs exactly $n$ times, and each time, a constant amount of work happens. Since this represents both an upper and a lower bound for the execution, the tight complexity is: \[ c \cdot n = \Theta(n) \]

For nested loops, we analyze from inside out, and the total running time is the product of the sizes of all the loops.

for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++)
        k = k + 1;   // constant time
}

The inner loop runs exactly $n$ times for each of the $n$ runs of the outer loop. Because this behavior is deterministic and constant across all inputs of size $n$, the tight running time is: \[ c \cdot n \cdot n = \Theta(n^2) \]

When statements come one after another, not nested, we simply add their time complexities.

x = x + 1;   // constant time
for (i = 1; i <= n; i++)
    m = m + 2;   // constant time
for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++)
        k = k + 1;   // constant time
}

Total time is: \[ c_0 + c_1 n + c_2 n^2 = \Theta(n^2) \] Here, the largest term, $c_2 n^2$, decides the final order of growth. The smaller terms do not matter for large $n$. Since the execution path always runs both loops, the runtime is tightly bounded by $\Theta(n^2)$.

For an if-else block, the worst-case time is the time for checking the condition, plus the larger of the two branches (the then-part or the else-part).

if (length() == 0)
    return false;      // constant
else {
    for (int n = 0; n < length(); n++) {
        if (list[n].equals(otherList.list[n]))
            return false;   // constant
    }
}

Here, the then part is constant time, but the worst-case scenario for the else part is that the loop runs to completion (taking time proportional to $n$). So, the worst-case complexity is tightly bounded by the else branch: \[ c_0 + c_1 + (c_2 + c_3)n = \Theta(n) \]

An algorithm takes $\Theta(\log n)$ time if its problem size gets divided or multiplied by a constant fraction each step, usually by $2$.

for (i = 1; i <= n; i = i * 2)
    ;   // constant time

Here, $i$ doubles every round, so after $k$ rounds, $i = 2^k$. The loop stops precisely when $2^k$ becomes bigger than $n$, which means: \[ 2^k = n \Rightarrow k = \log_2 n \] Since the loop always executes exactly $\lfloor \log_2 n \rfloor + 1$ iterations, its tight bound is $\Theta(\log n)$.

Similarly, dividing by $2$ every round also gives a tight bound of $\Theta(\log n)$:

for (i = n; i >= 1; i = i / 2)
    ;   // constant time

Find the time complexity of this code.

void function(int n) {
    int i, j, k, count = 0;
    for (i = n/2; i <= n; i++)
        for (j = 1; j + n/2 <= n; j++)
            for (k = 1; k <= n; k = k * 2)
                count++;
}

Outer loop: $i$ runs from $n/2$ to $n$, so the number of rounds is exactly $n - n/2 + 1 \approx n/2$, which is $\Theta(n)$.

Middle loop: The condition is $j + n/2 \le n$, which simplifies to $j \le n/2$. So this loop always runs exactly $n/2$ times, which is $\Theta(n)$.

Inner loop: $k$ doubles each round ($1, 2, 4, 8, \dots$) until it exceeds $n$. This always yields exactly $\lfloor \log_2 n \rfloor + 1$ rounds, which is $\Theta(\log n)$.

Combining all three loops: Since these nested loops execute unconditionally, we multiply their tight counts: \[ T(n) = \Theta(n) \times \Theta(n) \times \Theta(\log n) = \Theta(n^2 \log n) \]

Find the time complexity.

for (i = 1; i <= n; i = i + 2)
    count++;

Solution: The loop runs for $i = 1, 3, 5, \dots$, up to $n$, which is exactly $\lceil n/2 \rceil$ rounds. Ignoring the constant factor $\frac{1}{2}$, the tight asymptotic bound is $\Theta(n)$.

Find the time complexity.

for (i = 1; i <= n; i++)
    count++;
for (j = 1; j <= n*n; j++)
    count++;

Solution: The first loop takes exactly $\Theta(n)$ steps and the second loop takes exactly $\Theta(n^2)$ steps. Summing them together, the dominant quadratic term establishes a tight limit, so the total time complexity is $\Theta(n^2)$.

Find the time complexity.

for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j++)
        count++;

Solution: For each $i$, the inner loop runs exactly $i$ times. The total count is: \[ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \] which is $\Theta(n^2)$.

Find the time complexity.

for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j = j * 2)
        count++;

Solution: The outer loop runs exactly $n$ times ($\Theta(n)$). The inner loop runs exactly $\lfloor \log_2 n \rfloor + 1$ times ($\Theta(\log n)$) for each outer round. Since the work is fully deterministic, the total time complexity is tightly bounded: \[ \Theta(n) \times \Theta(\log n) = \Theta(n \log n) \]

Find the worst-case time complexity.

if (n % 2 == 0) {
    for (i = 1; i <= n; i++)
        count++;
} else {
    for (i = 1; i <= n*n; i++)
        count++;
}

Solution: When $n$ is even, the branch takes exactly $\Theta(n)$ time. When $n$ is odd, the branch takes exactly $\Theta(n^2)$ time. The worst-case performance is strictly determined by the odd branch, meaning the worst-case time complexity is tightly bounded by $\Theta(n^2)$.

This function adds up all numbers from $0$ to $n-1$.

This function counts how many pairs $(i, j)$ exist, where both $i$ and $j$ range from $0$ to $n-1$.

This function counts pairs $(i, j)$ where $j$ only goes up to $i$, not all the way to $n$.

This function counts how many times we can double a number, starting from $1$, before it crosses $n$.

This function has a simple loop, followed by a nested loop, one after another, not inside each other.

Step 1: Guess the answer. Based on similar problems, we guess \[ T(n) \le c \cdot n \log n,    \text{for some constant } c > 0 \]

Step 2: Assume the guess is true for smaller values. Assume for $n/2$, \[ T\left(\frac{n}{2}\right) \le c \cdot \frac{n}{2} \log\left(\frac{n}{2}\right) \]

Step 3: Substitute into the recurrence. \[ T(n) \le 2 \left( c \cdot \frac{n}{2} \log\left(\frac{n}{2}\right) \right) + n = c \cdot n \log\left(\frac{n}{2}\right) + n \] \[ = c \cdot n (\log n - 1) + n = c \cdot n \log n - c \cdot n + n \]

Step 4: Check the guess. We want \[ c \cdot n \log n - c \cdot n + n \le c \cdot n \log n \] This simplifies to $-c \cdot n + n \le 0$, that means $c \ge 1$. So, choosing $c \ge 1$ works.

Step 5: Conclude. Since a valid $c$ was found, $T(n) = O(n \log n)$. A similar argument with $\ge$ gives $T(n) = \Omega(n \log n)$. So, $T(n) = \Theta(n \log n)$.

Step 1: Guess the answer. We guess \[ T(n) \le c \cdot \log n,    \text{for some constant } c > 0 \]

Step 2: Assume the guess is true for $n/2$. \[ T\left(\frac{n}{2}\right) \le c \cdot \log\left(\frac{n}{2}\right) \]

Step 3: Substitute into the recurrence. \[ T(n) \le c \cdot \log\left(\frac{n}{2}\right) + 1 = c (\log n - 1) + 1 = c \log n - c + 1 \]

Step 4: Check the guess. We want \[ c \log n - c + 1 \le c \log n \] This simplifies to $-c + 1 \le 0$, that means $c \ge 1$. So, choosing $c \ge 1$ works.

Step 5: Conclude. So, $T(n) = O(\log n)$. A similar argument gives $T(n) = \Omega(\log n)$. So, $T(n) = \Theta(\log n)$.

Step 1: Guess the answer. We guess \[ T(n) \le c \cdot n^2,    \text{for some constant } c > 0 \]

Step 2: Assume the guess is true for $n/2$. \[ T\left(\frac{n}{2}\right) \le c \cdot \left(\frac{n}{2}\right)^2 = c \cdot \frac{n^2}{4} \]

Step 3: Substitute into the recurrence. \[ T(n) \le 2 \left( c \cdot \frac{n^2}{4} \right) + n^2 = \frac{c \cdot n^2}{2} + n^2 \]

Step 4: Check the guess. We want \[ \frac{c \cdot n^2}{2} + n^2 \le c \cdot n^2 \] This simplifies to $n^2 \le \dfrac{c \cdot n^2}{2}$, that means $c \ge 2$. So, choosing $c \ge 2$ works.

Step 5: Conclude. So, $T(n) = O(n^2)$. A similar argument gives $T(n) = \Omega(n^2)$. So, $T(n) = \Theta(n^2)$.

Step 1: Draw the root. The root is a problem of size $n$, with cost $n$ at that level.

Step 2: Draw the children. The root makes $2$ calls of size $n/2$ each. Level cost is $2 \times \dfrac{n}{2} = n$.

Step 3: Continue expanding. Each of those $2$ nodes makes $2$ calls of size $n/4$. Now $4$ nodes exist, each cost $n/4$, level total $4 \times \dfrac{n}{4} = n$.

Step 4: Notice the pattern. Every level costs exactly $n$, since problem size halves but number of nodes doubles, and these effects cancel.

Step 5: Count the levels. Size goes $n, n/2, n/4, \dots, 1$, giving $\log_2 n$ levels.

Step 6: Total cost. \[ T(n) = n \times \log_2 n = \Theta(n \log n) \]

Step 1: Draw the root. Root is size $n$, cost $n$.

Step 2: Draw children. Root makes $3$ calls of size $n/2$. Level cost $3 \times \dfrac{n}{2} = \dfrac{3n}{2}$.

Step 3: Continue expanding. Each of those $3$ nodes makes $3$ calls of size $n/4$, giving $9$ nodes, level cost $9 \times \dfrac{n}{4} = \dfrac{9n}{4}$.

Step 4: Notice the pattern. At level $i$, there are $3^i$ nodes, each of size $n/2^i$, so level cost is $3^i \times \dfrac{n}{2^i} = n \left(\dfrac{3}{2}\right)^i$. This level cost increases as $i$ increases, since $3/2 > 1$.

Step 5: Count the levels. Number of levels is $\log_2 n$, since size halves every level.

Step 6: Total cost. Since the cost grows with each level, the last level dominates the sum. The last level has $n^{\log_2 3}$ nodes, each doing constant work, giving \[ T(n) = \Theta(n^{\log_2 3}) \] which is approximately $\Theta(n^{1.58})$.

Step 1: Draw the root. Root is size $n$, cost $n$.

Step 2: Draw children. Root makes $2$ calls, one of size $n/2$, one of size $n/4$. Level cost is $\dfrac{n}{2} + \dfrac{n}{4} = \dfrac{3n}{4}$.

Step 3: Continue expanding. The $n/2$ node makes calls of size $n/4$ and $n/8$. The $n/4$ node makes calls of size $n/8$ and $n/16$. Level cost is again less than $n$, around $\dfrac{9n}{16}$.

Step 4: Notice the pattern. Unlike Example 2, here the level cost keeps shrinking, since $\dfrac{1}{2} + \dfrac{1}{4} = \dfrac{3}{4} < 1$. So the root level cost, $n$, dominates the total sum.

Step 5: Total cost. Adding up a shrinking sum across all levels still gives a value close to the root cost, just scaled by a constant. So, \[ T(n) = \Theta(n) \]

Step 1: Identify constants. $a = 2$, $b = 2$, $f(n) = n = \Theta(n^1 \log^0 n)$, so $k = 1$, $p = 0$.

Step 2: Compare $a$ with $b^k$. \[ a = 2,    b^k = 2^1 = 2    \Rightarrow    a = b^k \]

Step 3: Apply Case 2, check $p$. Since $p = 0 > -1$, use the first sub-case.

Step 4: Compute the answer. \[ T(n) = \Theta(n^{\log_2 2} \log^{0+1} n) = \Theta(n \log n) \]

Step 1: Identify constants. $a = 9$, $b = 3$, $f(n) = n = \Theta(n^1 \log^0 n)$, so $k = 1$, $p = 0$.

Step 2: Compare $a$ with $b^k$. \[ a = 9,    b^k = 3^1 = 3    \Rightarrow    a > b^k \]

Step 3: Apply Case 1. The leaves dominate since $a > b^k$.

Step 4: Compute the answer. \[ T(n) = \Theta(n^{\log_3 9}) = \Theta(n^2) \]

Step 1: Identify constants. $a = 3$, $b = 4$, $f(n) = n\log n = \Theta(n^1 \log^1 n)$, so $k = 1$, $p = 1$.

Step 2: Compare $a$ with $b^k$. \[ a = 3,    b^k = 4^1 = 4    \Rightarrow    a < b^k \]

Step 3: Apply Case 3, check $p$. Since $p = 1 \ge 0$, use the first sub-case.

Step 4: Compute the answer. \[ T(n) = \Theta(n^k \log^p n) = \Theta(n \log n) \]

Step 1: Identify constants. $a = 2$, $b = 2$, $f(n) = n \log n = \Theta(n^1 \log^1 n)$, so $k = 1$, $p = 1$.

Step 2: Compare $a$ with $b^k$. \[ a = 2,    b^k = 2^1 = 2    \Rightarrow    a = b^k \]

Step 3: Apply Case 2, check $p$. Since $p = 1 > -1$, use the first sub-case.

Step 4: Compute the answer. \[ T(n) = \Theta(n^{\log_2 2} \log^{1+1} n) = \Theta(n \log^2 n) \] This is exactly the recurrence that the basic Master Theorem could not solve, since $f(n) = n \log n$ sits exactly on $n^{\log_b a} = n$ with an extra log factor. The extended version handles it directly through the $p$ sub-case.

Solve $T(n) = 4T(n/2) + n$ using the Extended Master Theorem.

Solution: $a = 4$, $b = 2$, $f(n) = n = \Theta(n^1 \log^0 n)$, so $k = 1$, $p = 0$. $b^k = 2^1 = 2$. Since $a = 4 > b^k = 2$, this is Case 1, giving $T(n) = \Theta(n^{\log_2 4}) = \Theta(n^2)$.

Solve $T(n) = 2T(n/2) + n^2$ using the Extended Master Theorem.

Solution: $a = 2$, $b = 2$, $f(n) = n^2 = \Theta(n^2 \log^0 n)$, so $k = 2$, $p = 0$. $b^k = 2^2 = 4$. Since $a = 2 < b^k = 4$, this is Case 3, and $p = 0 \ge 0$, giving $T(n) = \Theta(n^2 \log^0 n) = \Theta(n^2)$.

Solve $T(n) = 8T(n/2) + n^2$ using the Extended Master Theorem.

Solution: $a = 8$, $b = 2$, $f(n) = n^2 = \Theta(n^2 \log^0 n)$, so $k = 2$, $p = 0$. $b^k = 2^2 = 4$. Since $a = 8 > b^k = 4$, this is Case 1, giving $T(n) = \Theta(n^{\log_2 8}) = \Theta(n^3)$.

Solve $T(n) = T(n/2) + n$ using the Extended Master Theorem.

Solution: $a = 1$, $b = 2$, $f(n) = n = \Theta(n^1 \log^0 n)$, so $k = 1$, $p = 0$. $b^k = 2^1 = 2$. Since $a = 1 < b^k = 2$, this is Case 3, and $p = 0 \ge 0$, giving $T(n) = \Theta(n^1 \log^0 n) = \Theta(n)$.

Solve $T(n) = 4T(n/2) + n \log^{-1} n$ using the Extended Master Theorem.

Solution: $a = 4$, $b = 2$, $f(n) = n\log^{-1} n = \Theta(n^1 \log^{-1} n)$, so $k = 1$, $p = -1$. $b^k = 2^1 = 2$. Since $a = 4 > b^k = 2$, this is Case 1, and Case 1 does not depend on $p$ at all, giving $T(n) = \Theta(n^{\log_2 4}) = \Theta(n^2)$.

Factorial of $n$, written $n!$, means multiplying all numbers from $n$ down to $1$. The recursive idea is, $n! = n \times (n-1)!$, and the base case is $0! = 1$. So, computing factorial of $n$ depends on computing factorial of $n-1$ first.

Factorial(n)

1. if n == 0

2.    return 1

3. else

4.    return n * Factorial(n - 1)

Step 1: Input size. The parameter $n$ is the input size.

Step 2: Basic operation. The multiplication, $n \times \text{Factorial}(n-1)$, is the basic operation.

Step 3: Recursive calls. Each call makes exactly $1$ recursive call, on input size $n-1$.

Step 4: Recurrence relation. \[ T(n) = T(n-1) + c,      T(0) = c \] Here, $c$ represents the constant work done outside the recursive call, like the multiplication and the comparison.

Step 5: Solve. Using the recursion tree method, each level reduces $n$ by $1$, and does constant work $c$. The tree has $n+1$ levels, from $n$ down to $0$. Total cost is \[ T(n) = c \times (n+1) = \Theta(n) \]

The Fibonacci sequence is $0, 1, 1, 2, 3, 5, 8, \dots$, where each number is the sum of the two numbers before it. The recursive idea is, $\text{Fib}(n) = \text{Fib}(n-1) + \text{Fib}(n-2)$, with base cases $\text{Fib}(0) = 0$ and $\text{Fib}(1) = 1$. Unlike factorial, here each call makes two recursive calls, not one.

Fibonacci(n)

1. if n $<=$ 1

2.    return n

3. else

4.    return Fibonacci(n - 1) + Fibonacci(n - 2)

Step 1: Input size. The parameter $n$ is the input size.

Step 2: Basic operation. The addition, combining the two recursive results, is the basic operation.

Step 3: Recursive calls. Each call makes $2$ recursive calls, one on $n-1$, one on $n-2$.

Step 4: Recurrence relation. \[ T(n) = T(n-1) + T(n-2) + c,      T(0) = T(1) = c \]

Step 5: Solve. This recurrence does not fit the Master Theorem, since the two subproblems have different sizes. Using the recursion tree method, each call branches into $2$ more calls, so the tree looks similar to a binary tree, except the depth on the left branch is longer than the right branch. The total number of nodes in this tree can be shown to grow like the Fibonacci numbers themselves, giving \[ T(n) = \Theta(\phi^n),      \phi \approx 1.618 \] where $\phi$ is the golden ratio. So, this simple looking function has exponential running time, $\Theta(2^n)$ is also commonly used as a simpler, looser bound for this.

This function adds up all the digits of a number $n$. The recursive idea is, the sum of digits of $n$ equals the last digit of $n$, plus the sum of digits of the remaining number, after removing the last digit. The base case is, when $n$ becomes $0$, the sum is $0$.

SumOfDigits(n)

1. if n == 0

2.    return 0

3. else

4.    return (n mod 10) + SumOfDigits(n / 10)

Step 1: Input size. Here, the input size is not $n$ itself, but the number of digits in $n$, since each call removes one digit, not one unit. Let us call the number of digits $d$.

Step 2: Basic operation. The addition, $(n \bmod 10) + \text{SumOfDigits}(n/10)$, is the basic operation.

Step 3: Recursive calls. Each call makes exactly $1$ recursive call, on a number with one less digit.

Step 4: Recurrence relation. \[ T(d) = T(d-1) + c,      T(0) = c \]

Step 5: Solve. Same pattern as factorial, each level does constant work, and there are $d+1$ levels. Total cost is \[ T(d) = \Theta(d) \] Since $d \approx \log_{10} n$, we can also write this as $\Theta(\log n)$, in terms of the value of $n$.

This function computes $x^n$, that is $x$ raised to power $n$. There are two ways to write this recursively, a slow way and a fast way. We look at both, to see how the recurrence changes the running time.

Here, $x^n = x \times x^{n-1}$, with base case $x^0 = 1$.

Here, we use the idea, $x^n = (x^{n/2})^2$, when $n$ is even, and $x^n = x \times (x^{(n-1)/2})^2$, when $n$ is odd. This way, the power reduces to half each time, instead of reducing by $1$.

PowerFast(x, n)

1. if n == 0

2.    return 1

3. else if n is even

4.    half = PowerFast(x, n / 2)

5.    return half * half

6. else

7.    half = PowerFast(x, (n - 1) / 2)

8.    return x * half * half

Step 1: Input size. The parameter $n$ is the input size.

Step 2: Basic operation. The multiplication, $half \times half$, is the basic operation.

Step 3: Recursive calls. Each call makes exactly $1$ recursive call, on input size roughly $n/2$.

Step 4: Recurrence relation. \[ T(n) = T(n/2) + c,      T(0) = c \]

Step 5: Solve using Master Theorem. Here, $a = 1$, $b = 2$, $f(n) = c = \Theta(1) = \Theta(n^0)$. Compute $n^{\log_b a} = n^{\log_2 1} = n^0$. Since $f(n)$ matches $n^{\log_b a}$ exactly, this is Case 2, giving \[ T(n) = \Theta(n^0 \log n) = \Theta(\log n) \] This shows the fast version is much better than the slow version, $\Theta(\log n)$ compared to $\Theta(n)$, just by halving the power instead of reducing it by $1$ each time.

A function reverses the digits of a number $n$ recursively, removing one digit and placing it at the end, in each call, until $n$ becomes $0$. Identify the recurrence and find the order of growth.

Solution: Each call reduces the number of digits by $1$, doing constant work. So, $T(d) = T(d-1) + c$, giving $T(d) = \Theta(d) = \Theta(\log n)$.

A function adds up all elements of an array of size $n$, by adding the first element to the sum of the rest of the array, recursively. Identify the recurrence and find the order of growth.

Solution: Each call reduces array size by $1$, doing constant work to add one element. So, $T(n) = T(n-1) + c$, giving $T(n) = \Theta(n)$.

The Tower of Hanoi problem moves $n$ disks, by first moving $n-1$ disks to a spare rod, then moving the largest disk, then moving the $n-1$ disks again, on top of it. Identify the recurrence and find the order of growth.

Solution: Each call makes $2$ recursive calls, each on size $n-1$, plus constant work for moving the largest disk. So, $T(n) = 2T(n-1) + c$. Solving by recursion tree, the tree doubles in nodes each level, while the work per node stays constant, giving $T(n) = \Theta(2^n)$.

A function prints numbers from $n$ down to $1$, by printing $n$, then calling itself on $n-1$. Identify the recurrence and find the order of growth.

Solution: Each call reduces $n$ by $1$, doing constant work for the print statement. So, $T(n) = T(n-1) + c$, giving $T(n) = \Theta(n)$.

A function computes the GCD of two numbers $a$ and $b$, using $\text{GCD}(a, b) = \text{GCD}(b, a \bmod b)$, until $b$ becomes $0$. This problem is harder to analyze directly using $n$ as size, since the reduction is not a simple halving or minus one, it depends on number theory properties.

Solution: It is known, using a deeper number theory result, that this recursion takes at most $O(\log(\min(a,b)))$ calls, because the smaller number reduces roughly by a multiplicative factor related to the golden ratio, in the worst case, every two calls.