Algorithm Basics and Analysis

This chapter establishes the foundational principles of algorithm analysis, critical for evaluating computational efficiency. Mastery of these concepts is indispensable for advanced algorithm design and optimization, forming a core component of the M.Sc./Ph.D. Computer Science CMI examination.

---

Chapter Contents

|

| Topic |

|---|-------| | 1 | Time and Space Complexity | | 2 | Best, Worst, and Average Case |

---

We begin with Time and Space Complexity.

Part 1: Time and Space Complexity

Understanding the efficiency of algorithms through time and space complexity analysis is fundamental for designing scalable and performant solutions in computer science. This topic provides the tools to evaluate and compare algorithms, crucial for CMI examinations.

---

Core Concepts

1. Asymptotic Notation

Asymptotic notation describes the limiting behavior of a function, providing a way to classify algorithms based on their growth rate as input size approaches infinity. We use Big-O, Omega, and Theta notation to express upper bounds, lower bounds, and tight bounds, respectively.

Worked Example: Proving Big-O

Show that $3n^2 + 2n + 5 = O(n^2)$.

Step 1: Identify $f(n)$ and $g(n)$.

> $f(n) = 3n^2 + 2n + 5$
> $g(n) = n^2$

Step 2: Find constants $c$ and $n_0$ such that $3n^2 + 2n + 5 \le c \cdot n^2$ for $n \ge n_0$.

> For $n \ge 1$:
> $3n^2 + 2n + 5 \le 3n^2 + 2n^2 + 5n^2$
> $3n^2 + 2n + 5 \le 10n^2$

Step 3: Choose $c$ and $n_0$.

> We can choose $c = 10$ and $n_0 = 1$.
> Thus, $3n^2 + 2n + 5 = O(n^2)$.

Answer: $3n^2 + 2n + 5 = O(n^2)$ is proven with $c=10, n_0=1$.

:::question type="MCQ" question="Which of the following statements is true for $f(n) = n \log n$ and $g(n) = n \sqrt{n}$?" options=["$f(n) = \Theta(g(n))$","$f(n) = O(g(n))$ but $f(n) \ne \Omega(g(n))$","$f(n) = \Omega(g(n))$ but $f(n) \ne O(g(n))$","Neither $f(n) = O(g(n))$ nor $f(n) = \Omega(g(n))$"] answer="$f(n) = O(g(n))$ but $f(n) \ne \Omega(g(n))$" hint="Compare the growth rates of $\log n$ and $\sqrt{n}$." solution="We need to compare $n \log n$ and $n \sqrt{n}$. This simplifies to comparing $\log n$ and $\sqrt{n}$.
We know that for sufficiently large $n$, $\log n < \sqrt{n}$.
Therefore, $n \log n < n \sqrt{n}$.
This implies $f(n) = O(g(n))$.
Since $\log n$ grows slower than $\sqrt{n}$, $f(n)$ cannot be bounded below by a constant multiple of $g(n)$, so $f(n) \ne \Omega(g(n))$.
Thus, $f(n) = O(g(n))$ but $f(n) \ne \Omega(g(n))$ is the correct statement."
:::

---

2. Analyzing Time Complexity of Iterative Algorithms

We analyze iterative algorithms by counting the number of basic operations (e.g., comparisons, assignments, arithmetic operations) as a function of the input size $n$. Summation notation is often used to express the total count of operations over loops.

Worked Example 1: Single Loop Analysis

Consider the function `g(int n)`:

```c
int g(int n) {
int a = 1;
int i = 0;
while (i < n) {
i = i + 1;
a = 2 * a;
}
return a;
}
```

Determine the time complexity of `g(n)`.

Step 1: Identify the loop and its iteration count.

> The `while` loop runs as long as `i < n`.
> The variable `i` starts at $0$ and increments by $1$ in each iteration.
> The loop executes $n$ times (for $i = 0, 1, \ldots, n-1$).

Step 2: Count operations inside the loop.

> Inside the loop: `i = i + 1` (1 assignment, 1 addition), `a = 2 * a` (1 assignment, 1 multiplication).
> Each iteration performs a constant number of operations.

Step 3: Calculate total operations.

> Total operations $\approx n \times (\text{constant operations per iteration})$.
> Total operations is $\Theta(n)$.

Answer: The time complexity of `g(n)` is $\Theta(n)$.

Worked Example 2: Nested Loops Analysis

Consider the `mystery` function:

```c
function mystery (A[0...99]) {
int i,j,m;
for (i = 0; i < 100; i++) {
m = i;
for (j = i; j < 100; j++) {
if (A[j] > A[m]) { // The test
m = j;
}
}
reverse(A,i,m); // Assume reverse(A,i,m) takes O(m-i+1) time
}
return;
}
```

Determine the number of times the test `A[j] > A[m]` is executed.

Step 1: Analyze the outer loop.

> The outer loop runs for `i` from $0$ to $99$. This is $100$ iterations.

Step 2: Analyze the inner loop for a given `i`.

> The inner loop runs for `j` from `i` to $99$.
> For `i = 0`, `j` runs from $0$ to $99$ ($100$ times).
> For `i = 1`, `j` runs from $1$ to $99$ ($99$ times).
> ...
> For `i = 99`, `j` runs from $99$ to $99$ ($1$ time).

Step 3: Sum the total number of test executions.

> Total tests = $\sum_{i=0}^{99} (\text{number of j iterations})$
> Total tests = $\sum_{k=1}^{100} k$ (where $k = 100-i$)
> Total tests = $100 + 99 + \cdots + 1$
> Total tests = $\frac{100 \times (100 + 1)}{2}$
> Total tests = $\frac{100 \times 101}{2}$
> Total tests = $50 \times 101$
> Total tests = $5050$

Answer: The test `A[j] > A[m]` is executed $5050$ times.

Worked Example 3: Analyzing a function with Fibonacci-like sequence

Consider the function `f(int n)`:

```c
int f(int n) {
int a, b, c, d;
a = 0; b = 0;
c = 0; d = 1;
while (a < n) {
a = a + 1;
b = b + c;
int temp = d;
d = c;
c = temp;
}
return b;
}
```

Determine the value returned by `f(100)`.

Step 1: Trace the variables `a`, `b`, `c`, `d` through iterations.

> Initial: $a=0, b=0, c=0, d=1$

| Iteration | `a` (before increment) | `a` (after increment) | `b` (after `b=b+c`) | `temp` | `d` (after `d=c`) | `c` (after `c=temp`) |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | $0+0=0$ | 1 | 0 | 1 |
| 1 | 1 | 2 | $0+1=1$ | 0 | 1 | 0 |
| 2 | 2 | 3 | $1+0=1$ | 1 | 0 | 1 |
| 3 | 3 | 4 | $1+1=2$ | 0 | 1 | 0 |
| 4 | 4 | 5 | $2+0=2$ | 1 | 0 | 1 |
| 5 | 5 | 6 | $2+1=3$ | 0 | 1 | 0 |
| 6 | 6 | 7 | $3+0=3$ | 1 | 0 | 1 |
| 7 | 7 | 8 | $3+1=4$ | 0 | 1 | 0 |
| 8 | 8 | 9 | $4+0=4$ | 1 | 0 | 1 |
| 9 | 9 | 10 | $4+1=5$ | 0 | 1 | 0 |

Step 2: Observe the pattern of `c` and `b`.

> `c` alternates between $0$ and $1$ (starting $0, 1, 0, 1, \dots$).
> `b` accumulates `c`.
> `b` sequence: $0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, \dots$
> `b` increments by $1$ every two iterations. Specifically, `b` increments by $1$ when `a` (after increment) is odd.

Step 3: Calculate `b` for `n=100`.

> The loop runs until `a` (after increment) reaches `n`. So, `a` takes values $1, 2, \dots, 100$.
> The value of `b` is updated $n$ times.
> `b` increments when `a` is $1, 3, 5, \dots, 99$.
> The number of odd values in this range is $(99-1)/2 + 1 = 49+1 = 50$.
> Therefore, `b` will sum $1$ for $50$ times, resulting in $50$.

Answer: `f(100)` returns $50$.

:::question type="MCQ" question="What is the time complexity of the following code snippet in terms of $n$?" options=["$O(n)$","$O(n \log n)$","$O(n^2)$","$O(\log n)$"] answer="$O(n^2)$" hint="Analyze the nested loop structure and how many times the inner loop executes for each outer loop iteration." solution="Step 1: Analyze the outer loop.
The outer loop `for (i = 0; i < n; i++)` runs $n$ times.

Step 2: Analyze the inner loop.
The inner loop `for (j = i; j < n; j++)` runs for `j` starting from `i` up to `n-1`.

• When `i = 0`, `j` runs $n$ times.


• When `i = 1`, `j` runs $n-1$ times.


• When `i = 2`, `j` runs $n-2$ times.


• ...


• When `i = n-1`, `j` runs $1$ time.

Step 3: Sum the operations.
The total number of times the innermost statement (e.g., `sum++`) is executed is the sum of an arithmetic series:

This sum is equal to $\frac{n(n+1)}{2}$.

Step 4: Determine the Big-O complexity.
$\frac{n(n+1)}{2} = \frac{n^2 + n}{2} = \frac{1}{2}n^2 + \frac{1}{2}n$.
The dominant term is $n^2$.
Therefore, the time complexity is $O(n^2)$.

```c
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
sum++;
}
}
```"
:::

---

3. Analyzing Time Complexity of Recursive Algorithms

Recursive algorithms are analyzed by formulating recurrence relations that describe the running time $T(n)$ in terms of the running time on smaller inputs. Common methods for solving recurrences include the Master Theorem, the Substitution Method, and the Recursion Tree Method.

Worked Example 1: Master Theorem Application

Solve the recurrence $T(n) = 2T(n/2) + n$.

Step 1: Identify $a, b,$ and $f(n)$.

> $a = 2$
> $b = 2$
> $f(n) = n$

Step 2: Calculate $n^{\log_b a}$.

> $n^{\log_2 2} = n^1 = n$.

Step 3: Compare $f(n)$ with $n^{\log_b a}$.

> $f(n) = n$ and $n^{\log_b a} = n$.
> This matches Case 2 of the Master Theorem: $f(n) = \Theta(n^{\log_b a})$.

Step 4: Apply the Master Theorem result.

> $T(n) = \Theta(n^{\log_b a} \log n) = \Theta(n \log n)$.

Answer: $T(n) = \Theta(n \log n)$.

Worked Example 2: Substitution Method

Solve the recurrence $T(n) = 2T(n/2) + 1$ with $T(1) = 1$.

Step 1: Guess the solution (using Master Theorem as a hint).

> For $T(n) = 2T(n/2) + 1$: $a=2, b=2, f(n)=1$.
> $n^{\log_b a} = n^{\log_2 2} = n^1 = n$.
> Since $f(n)=1 = O(n^{1-\epsilon})$ for $\epsilon=1$, this falls under Case 1, implying $T(n) = \Theta(n)$.
> Let's try to prove $T(n) \le cn - d$ for some constants $c, d$.

Step 2: Substitute the guess into the recurrence.

> Assume $T(k) \le ck - d$ for all $k < n$.
> $T(n) \le 2(c(n/2) - d) + 1$
> $T(n) \le cn - 2d + 1$

Step 3: Show that $T(n) \le cn - d$.

> We need $cn - 2d + 1 \le cn - d$.
> This implies $-2d + 1 \le -d$, or $1 \le d$. Let $d=1$.
> So, we need to show $T(n) \le cn - 1$.

Step 4: Verify base case and solve for $c$.

> For $n=1$, $T(1)=1$.
> $c(1) - 1 = 1 \implies c = 2$.
> So, our guess is $T(n) \le 2n - 1$.
> Let's substitute back: $T(n) \le 2(2(n/2)-1) + 1 = 2(n-1) + 1 = 2n-2+1 = 2n-1$.
> The guess holds.

Answer: $T(n) = \Theta(n)$.

:::question type="MCQ" question="What is the asymptotic time complexity of an algorithm whose recurrence relation is $T(n) = 3T(n/3) + n^2$?" options=["$O(n)$","$O(n \log n)$","$O(n^2)$","$O(n^3)$"] answer="$O(n^2)$" hint="Apply the Master Theorem. Compare $f(n)$ with $n^{\log_b a}$." solution="Step 1: Identify $a, b,$ and $f(n)$.
> $a = 3$
> $b = 3$
> $f(n) = n^2$

Step 2: Calculate $n^{\log_b a}$.
> $n^{\log_3 3} = n^1 = n$.

Step 3: Compare $f(n)$ with $n^{\log_b a}$.
> $f(n) = n^2$ and $n^{\log_b a} = n$.
> We observe that $n^2 = \Omega(n^{1+\epsilon})$ for $\epsilon = 1$.
> This matches Case 3 of the Master Theorem.

Step 4: Check regularity condition.
> We need to check if $a f(n/b) \le c f(n)$ for some constant $c < 1$.
> $3 \cdot (n/3)^2 = 3 \cdot n^2/9 = n^2/3$.
> We need $n^2/3 \le c n^2$. We can choose $c = 1/3 < 1$. The condition holds.

Step 5: Apply the Master Theorem result.
> $T(n) = \Theta(f(n)) = \Theta(n^2)$.
Therefore, the asymptotic time complexity is $O(n^2)$."
:::

---

4. Space Complexity Analysis

Space complexity quantifies the total amount of memory an algorithm requires to run, as a function of the input size $n$. It includes both auxiliary space (memory used by the algorithm itself, excluding input) and input space (memory required to store the input). In competitive programming, we often focus on auxiliary space.

Worked Example: Iterative vs. Recursive Factorial Space

Compare the auxiliary space complexity of iterative and recursive implementations of factorial.

Step 1: Iterative Factorial

```python
def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
```

> The variables `result`, `i`, and `n` each take constant space. No additional data structures grow with $n$.
> Auxiliary space complexity: $O(1)$.

Step 2: Recursive Factorial

```python
def factorial_recursive(n):
if n == 0:
return 1
else:
return n * factorial_recursive(n - 1)
```

> Each recursive call adds a stack frame to the call stack. This stack frame stores local variables and the return address.
> The depth of the recursion is $n$ (from $n$ down to $0$).
> Each stack frame takes constant space.
> Auxiliary space complexity: $O(n)$ due to the call stack.

Answer: Iterative factorial has $O(1)$ auxiliary space, while recursive factorial has $O(n)$ auxiliary space.

:::question type="MCQ" question="What is the auxiliary space complexity of the following function?" options=["$O(1)$","$O(\log n)$","$O(n)$","$O(n^2)$"] answer="$O(n)$" hint="Consider the data structure used and its size relative to the input $n$." solution="Step 1: Identify data structures that store elements.
The function `create_list` creates a list `my_list` and appends $n$ elements to it.

Step 2: Determine space used by `my_list`.
Each element added to `my_list` occupies constant space.
Since $n$ elements are added, the total space occupied by `my_list` is proportional to $n$.

Step 3: Determine auxiliary space.
The variable `i` and the list `my_list` are the primary memory consumers. `i` takes $O(1)$ space. `my_list` takes $O(n)$ space.
Thus, the dominant factor for auxiliary space is $O(n)$.

```python
def create_list(n):
my_list = []
for i in range(n):
my_list.append(i)
return my_list
```"
:::

---

5. Complexity Classes and Reductions

Complexity classes categorize problems based on the resources (time or space) required to solve them. Reductions are a fundamental tool to relate the difficulty of problems. If problem A can be reduced to problem B, it means that an efficient algorithm for B can be used to efficiently solve A.

Worked Example 1: Implications of Reductions

Suppose problem $A$ can be reduced to problem $B$ in polynomial time ($A \le_P B$). We know there is a polynomial-time algorithm to solve $B$. What can we conclude about problem $A$?

Step 1: Understand $A \le_P B$.

> This means an instance of $A$ can be transformed into an instance of $B$ in polynomial time ($T_{reduce}(n) = O(n^k)$).
> The size of the transformed instance $m$ must be polynomially bounded by $n$, i.e., $m = O(n^p)$ for some $p$.

Step 2: Combine reduction with solving $B$.

> If we have a polynomial-time algorithm for $B$ ($T_B(m) = O(m^j)$), then to solve $A$:
> 1. Transform $A$ instance (size $n$) to $B$ instance (size $m$) in $O(n^k)$ time.
> 2. Solve the $B$ instance in $O(m^j) = O((n^p)^j) = O(n^{pj})$ time.
> 3. The total time for $A$ is $O(n^k + n^{pj})$, which is polynomial in $n$.

Step 3: Conclude total time for $A$.

> Therefore, problem $A$ can also be solved in polynomial time.

Answer: If $A \le_P B$ and $B \in P$, then $A \in P$.

Worked Example 2: Modified Procedure Complexity

A procedure $P(n)$ makes multiple calls to $Q(m)$ and runs in polynomial time in $n$. $Q(m)$ is replaced by $R(m)$, which runs in exponential time in $m$. What conditions ensure $P(n)$ still runs in polynomial time?

Step 1: Analyze the original $P(n)$.

> $P(n)$ runs in polynomial time. Let its original complexity be $O(n^k)$.
> This means the total time spent in $P$'s own operations plus all calls to $Q(m)$ is $O(n^k)$.

Step 2: Analyze the impact of replacing $Q(m)$ with $R(m)$.

> $Q(m)$ was polynomial in $m$. $R(m)$ is exponential in $m$, e.g., $T_R(m) = O(c^m)$ for some constant $c>1$.

Step 3: Consider the total time for $P(n)$ with $R(m)$.

> The new total time for $P(n)$ would be (polynomial time for $P$'s own operations) + $\sum (\text{time for each call to } R(m))$.
> If $P$ makes $K$ calls to $R(m)$, and for each call, $m$ is some value $m_j$, the total time is $O(n^k + \sum_{j=1}^K c^{m_j})$.

Step 4: Identify conditions for polynomial time.

> For $P(n)$ to remain polynomial in $n$, the sum $\sum c^{m_j}$ must be polynomially bounded by $n$.
> If the number of calls $K$ is polynomial in $n$ (e.g., $K=O(n^q)$), then we need $c^{m_j}$ for each $m_j$ to not cause exponential growth in $n$.
> This happens if $m_j$ is bounded by a logarithmic function of $n$.
> Specifically, if $m_j \le \log_c n$ for all calls, then $c^{m_j} \le c^{\log_c n} = n$.
> In this case, each call to $R(m_j)$ takes $O(n)$ time.
> If there are $O(n^q)$ such calls, the total time for calls is $O(n^q \cdot n) = O(n^{q+1})$, which is polynomial in $n$.

Answer: $P(n)$ runs in polynomial time in $n$ if, for each call $Q(m)$, $m \le \log n$.

:::question type="MSQ" question="Given that problem $X$ is polynomial-time reducible to problem $Y$ ($X \le_P Y$), and problem $Y$ is known to be NP-complete. Which of the following statements are definitely true?" options=["Problem $X$ is also NP-complete.","Problem $X$ belongs to NP.","If $X$ is NP-complete, then $P=NP$.","If $Y$ can be solved in polynomial time, then $X$ can also be solved in polynomial time."] answer="Problem $X$ belongs to NP.,If $Y$ can be solved in polynomial time, then $X$ can also be solved in polynomial time." hint="Recall definitions of NP-completeness and the implications of polynomial-time reductions between complexity classes." solution="Analysis of options:

Problem $X$ is also NP-complete. Not necessarily. If $X \le_P Y$ and $Y$ is NP-complete, $X$ could be in $P$, or $X$ could be NP-complete, or $X$ could be in NP but not NP-complete (if $P \ne NP$). For $X$ to be NP-complete, it must also be in NP, and all problems in NP must be reducible to $X$. The reduction $X \le_P Y$ only tells us that $X$ is at most as hard* as $Y$ in terms of polynomial time.

* Problem $X$ belongs to NP. This is true. If $X \le_P Y$ and $Y$ is NP-complete, then $Y \in NP$. Since $X$ reduces to $Y$, and $Y$ is verifiable in polynomial time, then $X$ is also verifiable in polynomial time (by first reducing $X$ to $Y$, then verifying $Y$'s solution). Therefore, $X \in NP$.

* If $X$ is NP-complete, then $P=NP$. This is false. This statement should be 'If $Y$ is NP-complete and $Y \in P$, then $P=NP$'. If $X$ is NP-complete, it means $X$ is one of the hardest problems in NP. If $X$ could be solved in polynomial time, then $P=NP$. The statement as written is not definitely true.

* If $Y$ can be solved in polynomial time, then $X$ can also be solved in polynomial time. This is true. This is the direct implication of a polynomial-time reduction. If $X \le_P Y$ and $Y$ has a polynomial-time algorithm, then we can solve $X$ by transforming it to $Y$ (polynomial time) and solving $Y$ (polynomial time), resulting in an overall polynomial-time algorithm for $X$.

Thus, 'Problem $X$ belongs to NP.' and 'If $Y$ can be solved in polynomial time, then $X$ can also be solved in polynomial time.' are the definitely true statements."
:::

---

Advanced Applications

Worked Example: Combined Analysis of Reduction and Exponential Algorithms

We have constructed a polynomial time reduction from problem $A$ to problem $B$. Consider the implications for the existence of algorithms.

Step 1: Define the reduction $A \le_P B$.

> This means if $B$ can be solved in polynomial time, then $A$ can also be solved in polynomial time.
> Equivalently, if $A$ cannot be solved in polynomial time (i.e., requires exponential time), then $B$ also cannot be solved in polynomial time (must also require exponential time).

Step 2: Analyze the scenarios.

> Scenario 1: We know of polynomial time algorithms for both $A$ and $B$.
> * Possible. If $B \in P$, then $A \in P$. This is consistent.

> Scenario 2: We only know of exponential time algorithms for both $A$ and $B$.
> * Possible. If $B \notin P$, then $A$ could also be $\notin P$. This is consistent.

> Scenario 3: We only know of an exponential time algorithm for $A$, but we have a polynomial time algorithm for $B$.
> This scenario is NOT possible. If $B$ has a polynomial-time algorithm, then by the reduction $A \le_P B$, $A$ must also have a polynomial-time algorithm. It cannot only* have an exponential-time algorithm.

> Scenario 4: We only know of an exponential time algorithm for $B$, but we have a polynomial time algorithm for $A$.
> * Possible. $A \le_P B$ means $B$ is at least as hard as $A$. If $A \in P$, $B$ could still be harder (e.g., $B \notin P$). This is consistent. For example, $3-SAT \le_P SAT$. If $P \ne NP$, both are exponential. But if $A$ is a trivial problem in $P$ and $B$ is NP-complete, this situation is possible.

Answer: The scenario that is not possible is: "We only know of an exponential time algorithm for $A$, but we have a polynomial time algorithm for $B$."

:::question type="MCQ" question="An algorithm has a time complexity of $T(n) = T(n-1) + O(n)$ with $T(1)=O(1)$. What is its overall time complexity?" options=["$O(n)$","$O(n \log n)$","$O(n^2)$","$O(2^n)$"] answer="$O(n^2)$" hint="Use the substitution method or expand the recurrence." solution="Step 1: Expand the recurrence.
> $T(n) = T(n-1) + cn$ (for some constant $c$)
> $T(n-1) = T(n-2) + c(n-1)$
> $T(n-2) = T(n-3) + c(n-2)$
> ...
> $T(2) = T(1) + c(2)$

Step 2: Substitute backwards.
> $T(n) = T(n-2) + c(n-1) + cn$
> $T(n) = T(n-3) + c(n-2) + c(n-1) + cn$
> Continuing this pattern, we get:
> $T(n) = T(1) + c(2) + c(3) + \cdots + c(n-1) + cn$

Step 3: Sum the series.
> $T(n) = O(1) + c \sum_{i=2}^{n} i$
> The sum $\sum_{i=2}^{n} i = \frac{n(n+1)}{2} - 1$.

Step 4: Determine the asymptotic complexity.
> $T(n) = O(1) + c \left( \frac{n^2 + n}{2} - 1 \right)$
> $T(n) = O(n^2)$.
Therefore, the overall time complexity is $O(n^2)$."
:::

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Which of the following functions grows fastest asymptotically?" options=["$n \log n$","$n^{1.5}$","$2^{\sqrt{\log n}}$","$(\log n)^2$"] answer="$n^{1.5}$" hint="Compare the growth rates by taking logarithms or raising to powers to simplify comparison." solution="We need to compare the growth rates of the four functions.

$f_1(n) = n \log n$

$f_2(n) = n^{1.5}$

$f_3(n) = 2^{\sqrt{\log n}}$

$f_4(n) = (\log n)^2$

Let's compare them:
* $n^{1.5}$ vs $n \log n$: $n^{1.5} = n \cdot n^{0.5} = n \sqrt{n}$. Since $\sqrt{n}$ grows faster than $\log n$, $n^{1.5}$ grows faster than $n \log n$.
* $n^{1.5}$ vs $(\log n)^2$: Any polynomial $n^k$ (for $k>0$) grows faster than any polylogarithmic function $(\log n)^p$. So $n^{1.5}$ grows much faster than $(\log n)^2$.
*$n^{1.5}$ vs $2^{\sqrt{\log n}}$**: To compare these, let $k = \log n$, so $n = 2^k$.
* $n^{1.5} = (2^k)^{1.5} = 2^{1.5k}$
* $2^{\sqrt{\log n}} = 2^{\sqrt{k}}$
Since $k$ grows faster than $\sqrt{k}$ for large $k$, $2^{1.5k}$ grows much faster than $2^{\sqrt{k}}$.
Therefore, $n^{1.5}$ grows faster than $2^{\sqrt{\log n}}$.

Comparing all, $n^{1.5}$ is the fastest growing function."
:::

:::question type="NAT" question="What is the result of the `count` variable after the execution of the following code for $N=64$?" answer="321" hint="Analyze the inner loop's condition and increment, and then sum the iterations over the outer loop." solution="Step 1: Analyze the outer loop.
The outer loop `for (int i = 1; i <= N; i++)` runs $N$ times. For $N=64$, it runs $64$ times.

Step 2: Analyze the inner loop.
The inner loop `for (int j = 1; j < i; j = j * 2)` depends on the value of `i`.
The variable `j` takes values $1, 2, 4, \ldots, 2^k$ such that $2^k < i$.
The number of iterations for the inner loop, for a given `i > 1`, is the number of powers of 2 strictly less than `i`. This is $\lfloor \log_2 (i-1) \rfloor + 1$.
For $i=1$, the inner loop condition `j < i` (i.e., `1 < 1`) is false, so it runs 0 times.

Let's calculate the number of inner loop iterations for each `i` from $1$ to $64$:
* `i=1`: 0 iterations.
* `i=2`: `j=1`. (1 iteration). $\lfloor \log_2(1) \rfloor + 1 = 1$.
* `i=3`: `j=1,2`. (2 iterations). $\lfloor \log_2(2) \rfloor + 1 = 2$.
* `i=4`: `j=1,2`. (2 iterations). $\lfloor \log_2(3) \rfloor + 1 = 2$.
* `i=5`: `j=1,2,4`. (3 iterations). $\lfloor \log_2(4) \rfloor + 1 = 3$.
* ...
* `i=64`: `j=1,2,4,8,16,32`. (6 iterations). $\lfloor \log_2(63) \rfloor + 1 = 6$.

Step 3: Sum the total `count`.
We need to sum the number of inner loop iterations for each `i` from $1$ to $64$.
The number of times `k` iterations occur:
* $k=1$: for $i=2$ (1 value)
* $k=2$: for $i \in [3,4]$ (2 values)
* $k=3$: for $i \in [5,8]$ (4 values)
* $k=4$: for $i \in [9,16]$ (8 values)
* $k=5$: for $i \in [17,32]$ (16 values)
* $k=6$: for $i \in [33,64]$ (32 values)

Total `count` = $(1 \times 1) + (2 \times 2) + (3 \times 4) + (4 \times 8) + (5 \times 16) + (6 \times 32)$
Total `count` = $1 + 4 + 12 + 32 + 80 + 192$
Total `count` = $321$.

```c
int calculate(int N) {
int count = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j < i; j = j * 2) {
count++;
}
}
return count;
}
```"
:::

:::question type="MSQ" question="Which of the following statements are true about the relationship between $P$ and $NP$?" options=["If $P=NP$, then all problems in $NP$ can be solved in polynomial time by a deterministic algorithm.","If an NP-complete problem can be solved in polynomial time, then $P=NP$.","Every problem in $P$ is also in $NP$.","Every problem in $NP$ is also in $P$."] answer="If $P=NP$, then all problems in $NP$ can be solved in polynomial time by a deterministic algorithm.,If an NP-complete problem can be solved in polynomial time, then $P=NP$.,Every problem in $P$ is also in $NP$." hint="Recall the definitions of P, NP, and NP-completeness, and their known relationships." solution="Analysis of options:

* If $P=NP$, then all problems in $NP$ can be solved in polynomial time by a deterministic algorithm. This is true by definition. If $P=NP$, it means that the class of problems verifiable in polynomial time ($NP$) is equivalent to the class of problems solvable in polynomial time by a deterministic algorithm ($P$).

* If an NP-complete problem can be solved in polynomial time, then $P=NP$. This is true. If an NP-complete problem (which is by definition the 'hardest' problem in NP, in the sense that all problems in NP can be reduced to it) can be solved in polynomial time, then by applying the polynomial-time reduction, every problem in NP can also be solved in polynomial time. This implies $NP \subseteq P$. Since $P \subseteq NP$ is always true, it would mean $P=NP$.

* Every problem in $P$ is also in $NP$. This is true. If a problem can be solved in polynomial time by a deterministic algorithm ($P$), then a solution can certainly be verified in polynomial time (we can just solve it and check if the solution is correct). Thus, $P \subseteq NP$.

Every problem in $NP$ is also in $P$. This is the famous $P=NP$ question. It is not known* to be true; it is an open problem in computer science. If this were true, it would imply $P=NP$.

Thus, the first three statements are definitely true."
:::

:::question type="MCQ" question="What is the space complexity of a recursive function that calculates the $n$-th Fibonacci number, $F(n) = F(n-1) + F(n-2)$, using a standard recursive implementation without memoization?" options=["$O(1)$","$O(\log n)$","$O(n)$","$O(n^2)$"] answer="$O(n)$" hint="Consider the maximum depth of the recursion call stack." solution="Step 1: Analyze the recursion depth.
The standard recursive implementation of Fibonacci numbers (e.g., `fib(n) = fib(n-1) + fib(n-2)`) makes two recursive calls.
The depth of the recursion stack is determined by the longest chain of calls.
The longest chain of calls is `fib(n) -> fib(n-1) -> fib(n-2) -> ... -> fib(1)`.
This chain has a depth proportional to $n$.

Step 2: Space per stack frame.
Each recursive call adds a stack frame to the call stack. This frame stores local variables and the return address. Each stack frame consumes a constant amount of memory.

Step 3: Total space complexity.
Since the maximum depth of the recursion stack is $O(n)$, and each stack frame takes $O(1)$ space, the total auxiliary space complexity is $O(n) \times O(1) = O(n)$.
"
:::

:::question type="MCQ" question="An algorithm has a time complexity described by the recurrence $T(n) = 4T(n/2) + n^3$. What is its asymptotic time complexity?" options=["$O(n^2)$","$O(n^2 \log n)$","$O(n^3)$","$O(n^4)$"] answer="$O(n^3)$" hint="Apply the Master Theorem, comparing $f(n)$ with $n^{\log_b a}$." solution="Step 1: Identify $a, b,$ and $f(n)$.
> $a = 4$
> $b = 2$
> $f(n) = n^3$

Step 2: Calculate $n^{\log_b a}$.
> $n^{\log_2 4} = n^2$.

Step 3: Compare $f(n)$ with $n^{\log_b a}$.
> $f(n) = n^3$ and $n^{\log_b a} = n^2$.
> We observe that $n^3 = \Omega(n^{2+\epsilon})$ for $\epsilon = 1$.
> This matches Case 3 of the Master Theorem.

Step 4: Check regularity condition.
> We need to check if $a f(n/b) \le c f(n)$ for some constant $c < 1$.
> $4 \cdot (n/2)^3 = 4 \cdot n^3/8 = n^3/2$.
> We need $n^3/2 \le c n^3$. We can choose $c = 1/2 < 1$. The condition holds.

Step 5: Apply the Master Theorem result.
> $T(n) = \Theta(f(n)) = \Theta(n^3)$.
Therefore, the asymptotic time complexity is $O(n^3)$."
:::

---

Summary

---

What's Next?

---

---

Part 2: Best, Worst, and Average Case

Algorithm analysis often requires evaluating performance across various input scenarios to understand its practical implications. We define best, worst, and average cases to characterize an algorithm's efficiency bounds.

---

Core Concepts

1. Best Case Analysis

We define the best case of an algorithm as the scenario where it performs the minimum number of operations for a given input size $n$. This represents the most favorable input.

Worked Example: Linear Search

Consider an algorithm `LinearSearch(A, x)` that searches for an element $x$ in an array $A$ of size $n$.

Step 1: Define the algorithm

```
function LinearSearch(A, x):
n = length(A)
for i from 1 to n:
if A[i] == x:
return i // Element found
return -1 // Element not found
```

Step 2: Identify the best-case input

The best case occurs when the target element $x$ is found at the first position of the array. The loop executes only once.

>

Answer: The best-case time complexity for Linear Search is $O(1)$.

:::question type="MCQ" question="For a sorting algorithm that checks if an array is already sorted before performing any major sorting operations, what is the best-case time complexity if the input array is already sorted?" options=["$O(1)$","$O(\log n)$","$O(n)$","$O(n \log n)$"] answer="$O(n)$" hint="Checking if an array of size $n$ is sorted requires iterating through all elements once." solution="Step 1: Analyze the 'check sorted' operation.
To verify if an array $A$ of size $n$ is sorted, we must iterate from $A[1]$ to $A[n-1]$ and check if $A[i] \le A[i+1]$ for all $i$. This takes $O(n)$ time.

Step 2: Determine the total complexity.
If the array is already sorted, the algorithm performs this $O(n)$ check and then terminates without further sorting.

>

"
:::

---

2. Worst Case Analysis

We define the worst case as the scenario where an algorithm performs the maximum number of operations for a given input size $n$. This provides an upper bound on the algorithm's runtime.

Worked Example 1: Linear Search

Consider the `LinearSearch(A, x)` algorithm.

Step 1: Identify the worst-case input

The worst case occurs when the target element $x$ is either at the last position of the array or not present in the array at all. The loop iterates through all $n$ elements.

>

Answer: The worst-case time complexity for Linear Search is $O(n)$.

Worked Example 2: Recursive Selection Algorithm (Inspired by PYQ 3 & 4)

Consider the `mystery` function which attempts to find the $k$-th smallest element in an array $A$.

```
function mystery(A, k) {
n = length(A);
if (k > n) return A[n];

v = A[1]; // Pivot is always the first element
AL = [ A[j] : 1 <= j <= n, A[j] < v ];
AV = [ A[j] : 1 <= j <= n, A[j] == v ];
AR = [ A[j] : 1 <= j <= n, A[j] > v ];

if (length(AL) >= k) return mystery(AL, k);
if (length(AL) + length(AV) > k) return v;
return mystery(AR, k - (length(AL) + length(AV)));
}
```

Step 1: Analyze the operations at each step.

At each recursive call, the algorithm scans the entire current array to partition it into `AL`, `AV`, and `AR`. This partitioning takes $O(m)$ time, where $m$ is the length of the current array.

Step 2: Identify the worst-case input for the pivot choice.

The worst case occurs when the pivot $v=A[1]$ is consistently chosen as the smallest or largest element in the array. This leads to highly unbalanced partitions.

Consider $A = [1, 2, 3, \dots, n]$ and we search for $k=n$.

• First call: $v=1$. `AL` is empty, `AV` contains `[1]`, `AR` contains `[2, 3, \dots, n]`.


• The recursive call is `mystery(AR, n-1)`, where `AR` has size $n-1$.


• This pattern continues, with the array size decreasing by only one element in each recursive call.

Step 3: Formulate the recurrence relation.

Let $T(n)$ be the time complexity for an input of size $n$. In the worst case, the partitioning takes $O(n)$ and the recursive call is made on an array of size $n-1$.

>

Step 4: Solve the recurrence relation.

>

Answer: The worst-case time complexity is $O(n^2)$. An example worst-case input is an already sorted array $A = [1, 2, \dots, n]$ searching for the $n$-th element, or a reverse-sorted array $A = [n, n-1, \dots, 1]$ searching for the 1st element.

:::question type="MCQ" question="Consider a search algorithm for an $n \times n$ matrix $A$ where each row and column is sorted in ascending order. The algorithm starts at $A[1,n]$ (top-right corner) and searches for $k$. If $A[i,j] = k$, it returns $(i,j)$. If $A[i,j] < k$, it moves down to $A[i+1,j]$. If $A[i,j] > k$, it moves left to $A[i,j-1]$. What is a worst-case input for this algorithm if $k$ is present?" options=["$k$ is at $A[1,1]$","$k$ is at $A[n,n]$","$k$ is at $A[1,n]$","$k$ is at $A[n,1]$"] answer="$k$ is at $A[n,1]$" hint="Analyze the movement pattern. To reach $A[n,1]$ from $A[1,n]$, the algorithm must traverse the maximum number of rows and columns." solution="Step 1: Understand the search strategy.
Starting at $(1,n)$:

• If current element is less than $k$, move down (increase row index).


• If current element is greater than $k$, move left (decrease column index).


• If current element equals $k$, found.

Step 2: Identify the path for maximum operations.
To maximize operations, the algorithm should be forced to traverse as many rows and columns as possible.

• To move down $n-1$ times, $k$ must be greater than or equal to elements in $A[1,j], A[2,j], \dots, A[n-1,j]$.


• To move left $n-1$ times, $k$ must be less than or equal to elements in $A[i,n], A[i,n-1], \dots, A[i,2]$.

Consider $k$ at $A[n,1]$.
The algorithm starts at $A[1,n]$. To reach $A[n,1]$, it must make $n-1$ 'down' moves and $n-1$ 'left' moves. This requires $2n-2$ comparisons in the worst case. For example, if all elements in the first column are less than $k$, it will move down until $A[n,n]$. Then, if $A[n,j] > k$ for $j > 1$, it will move left until $A[n,1]$. This path covers the maximum number of steps.

>

>

"
:::

---

3. Average Case Analysis

We define the average case as the expected number of operations for a given input size $n$, assuming a specific probability distribution over all possible inputs. This requires probabilistic analysis.

Worked Example: Linear Search (Average Case)

Consider `LinearSearch(A, x)` on an array $A$ of size $n$. We assume the following:

The element $x$ is present in the array with probability $p$.

If $x$ is present, it is equally likely to be at any of the $n$ positions (i.e., probability $1/n$ for each position).

If $x$ is not present (probability $1-p$), the algorithm performs $n$ comparisons.

Step 1: Calculate the expected number of comparisons if $x$ is present.

If $x$ is at position $i$, it takes $i$ comparisons.
The probability of $x$ being at position $i$ given it's present is $1/n$.

>

Step 2: Calculate the total average number of comparisons.

>

Answer: The average-case time complexity is $O(n)$. For $p=1$ (always present), it's $O(n/2) = O(n)$. For $p=0$ (never present), it's $O(n)$.

:::question type="NAT" question="A hash table uses chaining to resolve collisions. The load factor is $\alpha = N/M$, where $N$ is the number of items and $M$ is the number of slots. Assuming simple uniform hashing, what is the average number of probes (comparisons) for an unsuccessful search?" answer="alpha" hint="In simple uniform hashing, each item is equally likely to be hashed into any slot. An unsuccessful search must traverse the entire chain at the hashed slot." solution="Step 1: Understand simple uniform hashing and unsuccessful search.
Simple uniform hashing implies that any given item is equally likely to hash into any of the $M$ slots, independently of where other items hash.
For an unsuccessful search, we hash the key to a slot $j$. If slot $j$ has a chain of length $L_j$, we must traverse all $L_j$ elements in that chain to confirm the key is not present.

Step 2: Calculate the expected chain length.
The expected length of a chain at any given slot $j$ is the total number of items $N$ divided by the total number of slots $M$. This is the definition of the load factor $\alpha$.

>

Step 3: Determine the average probes.
Since an unsuccessful search must traverse the entire chain at its hashed slot, the average number of probes is equal to the average chain length.

>

"
:::

---

Advanced Applications

1. Concurrent Execution Outcomes

When multiple processes access and modify shared variables concurrently, the final state can depend on the interleaving of operations. We analyze best (minimum) and worst (maximum) possible outcomes by considering all valid execution schedules.

Worked Example: Shared Variable Update (Inspired by PYQ 1)

Consider two procedures, `proc1` and `proc2`, running in parallel. `x` is a shared variable initialized to $0$.

```c
int x = 0;

proc1 {
int temp1 = x;
x = temp1 + 1;
temp1 = x;
x = temp1 + 1;
}

proc2 {
int temp2 = x;
x = temp2 + 1;
}
```

Step 1: Analyze `proc1` operations without interference.

If `proc1` runs alone:

`temp1 = x;` (temp1 = 0)

`x = temp1 + 1;` (x = 1)

`temp1 = x;` (temp1 = 1)

`x = temp1 + 1;` (x = 2)

Final `x = 2`.

Step 2: Analyze `proc2` operations without interference.

If `proc2` runs alone:

`temp2 = x;` (temp2 = 0)

`x = temp2 + 1;` (x = 1)

Final `x = 1`.

Step 3: Identify the minimum possible value for `x`.

To get the minimum value, we want `temp` variables to read `x` when it is as small as possible, and then for updates to overwrite each other.

Consider `proc1` reads `x` (0), then `proc2` reads `x` (0), then both write back.

> Interleaving for Minimum `x`:
>
> 1. `proc1`: `temp1 = x;` ($\text{temp1}=0$)
> 2. `proc2`: `temp2 = x;` ($\text{temp2}=0$)
> 3. `proc1`: `x = temp1 + 1;` ($x=1$)
> 4. `proc2`: `x = temp2 + 1;` ($x=1$)
> 5. `proc1`: `temp1 = x;` ($\text{temp1}=1$)
> 6. `proc1`: `x = temp1 + 1;` ($x=2$)

In this interleaving, `x` becomes 2. This is not the minimum. A smaller value can be achieved if `proc2`'s `x = temp2 + 1` overwrites `proc1`'s first increment before `proc1` reads `x` again.

> Revised Interleaving for Minimum `x`:
>
> 1. `proc1`: `temp1 = x;` ($\text{temp1}=0$)
> 2. `proc2`: `temp2 = x;` ($\text{temp2}=0$)
> 3. `proc2`: `x = temp2 + 1;` ($x=1$)
> 4. `proc1`: `x = temp1 + 1;` ($x=1$) // `proc1` writes 1, overwriting `proc2`'s 1.
> 5. `proc1`: `temp1 = x;` ($\text{temp1}=1$)
> 6. `proc1`: `x = temp1 + 1;` ($x=2$)

In this scenario, `x` becomes 2. Let's trace more carefully to find a smaller value. The key is when a `temp` variable reads an outdated `x`.

> Minimum possible `x = 1`:
>
> 1. `proc1`: `temp1 = x;` ($\text{temp1}=0$)
> 2. `proc1`: `x = temp1 + 1;` ($x=1$)
> 3. `proc2`: `temp2 = x;` ($\text{temp2}=1$)
> 4. `proc2`: `x = temp2 + 1;` ($x=2$)
> 5. `proc1`: `temp1 = x;` ($\text{temp1}=2$)
> 6. `proc1`: `x = temp1 + 1;` ($x=3$)
>
> This gives 3. The minimum occurs if one process's final write is based on an old value.

> Correct Minimum `x = 1`:
>
> 1. `proc1`: `temp1 = x;` ($\text{temp1}=0$)
> 2. `proc2`: `temp2 = x;` ($\text{temp2}=0$)
> 3. `proc1`: `x = temp1 + 1;` ($x=1$)
> 4. `proc1`: `temp1 = x;` ($\text{temp1}=1$)
> 5. `proc1`: `x = temp1 + 1;` ($x=2$)
> 6. `proc2`: `x = temp2 + 1;` ($x=1$) // `proc2` writes 1, based on its initial read of 0. This is the last operation.

Step 4: Identify the maximum possible value for `x`.

To get the maximum value, we want each increment to be based on the most up-to-date value of `x`. This means allowing one process to fully complete its increments, then the other.

> Interleaving for Maximum `x = 3`:
>
> 1. `proc1` fully executes:
> - `temp1 = x;` ($\text{temp1}=0$)
> - `x = temp1 + 1;` ($x=1$)
> - `temp1 = x;` ($\text{temp1}=1$)
> - `x = temp1 + 1;` ($x=2$)
> 2. `proc2` fully executes:
> - `temp2 = x;` ($\text{temp2}=2$)
> - `x = temp2 + 1;` ($x=3$)

Answer: The possible values for $x$ are $1, 2, 3$.
Minimum possible value for `x` is $1$.
Maximum possible value for `x` is $3$.

:::question type="MCQ" question="Consider $x=0$. `procA` performs `x = x + 1; x = x + 1;`. `procB` performs `x = x + 1;`. Both run concurrently. Which of the following values are possible for $x$ after both processes halt?" options=["1","2","3","4"] answer="2,3" hint="Trace interleavings. Identify the minimum and maximum possible outcomes. A value of 1 implies one of the increments was completely lost, which is not possible with these operations." solution="Step 1: Analyze `procA` and `procB` independently.
`procA` intends to add 2 to $x$.
`procB` intends to add 1 to $x$.
Total intended increments: 3.

Step 2: Determine the minimum possible value.
A common way to get a minimum value is if a `read-modify-write` sequence is interrupted, and an older value is written back, effectively losing an increment.

• Start: $x=0$


• `procA`: `x = x + 1;` ($x=1$)


• `procB`: `x = x + 1;` ($x=2$)


• `procA`: `x = x + 1;` ($x=3$)

This is 3.
Consider:

• `procA` reads $x=0$.


• `procB` reads $x=0$.


• `procA` writes $x=1$.


• `procA` reads $x=1$.


• `procB` writes $x=1$. // `procB`'s write based on $x=0$ overwrites `procA`'s previous write.


• `procA` writes $x=2$.

Final $x=2$. This is the minimum.

Step 3: Determine the maximum possible value.
The maximum value occurs when all increments are applied sequentially without any overwrites based on stale reads.

• `procA` fully executes: $x \to 0 \to 1 \to 2$.


• Then `procB` executes: $x \to 2 \to 3$.

Final $x=3$.

Step 4: List all possible values.
The possible values are $2$ and $3$.

>

"
:::

2. Amortized Analysis

We use amortized analysis to analyze the performance of a sequence of operations, where a single operation might be expensive, but the average cost over a long sequence of operations is low. It provides a worst-case guarantee on the average performance per operation.

Worked Example: Dynamic Array (Vector) Append Operation

Consider a dynamic array that doubles its capacity when it runs out of space. Appending an element usually takes $O(1)$ time, but when a reallocation occurs, it takes $O(N)$ time, where $N$ is the current number of elements.

Step 1: Analyze the cost of a sequence of $N$ `append` operations.

Let's start with an empty array of capacity 1.

• `append(1)`: Cost 1 (copy 0 elements, add 1). Capacity 1 -> 2.


• `append(2)`: Cost 1 (add 1). Capacity 2.


• `append(3)`: Cost 3 (copy 2 elements, add 1). Capacity 2 -> 4.


• `append(4)`: Cost 1 (add 1). Capacity 4.


• `append(5)`: Cost 5 (copy 4 elements, add 1). Capacity 4 -> 8.

The reallocations occur when the number of elements reaches $2^k+1$.
The cost for $N$ appends is the sum of costs for individual appends.
The costs for reallocations are $1$ (for capacity 1 to 2), $2$ (for capacity 2 to 4), $4$ (for capacity 4 to 8), $\dots$, $2^k$ (for capacity $2^k$ to $2^{k+1}$).
The total cost for $N$ appends (where $N = 2^k$) would be approximately:

>

Since $N=2^k$, the sum is $N-1+N = 2N-1$. More accurately, for $N$ appends, the last reallocation might not be fully accounted for by this sum.
A more general summation for $N$ elements: $1 + 2 + 4 + \dots + 2^{\lfloor \log_2 (N-1) \rfloor} + (\text{N - number of reallocations})$.
The total cost for $N$ appends is roughly $N + \sum_{j=1}^{\log N} 2^{j-1}$. This sum is $N + (N-1) \approx 2N$.

Step 2: Calculate the amortized cost.

The total cost for $N$ appends is $O(N)$.

>

Answer: The amortized time complexity of the `append` operation for a dynamic array is $O(1)$.

:::question type="MCQ" question="A stack supports `PUSH(x)` (cost 1) and `MULTIPOP(k)` (pops $k$ elements or until empty, cost $k$). What is the amortized cost of a `MULTIPOP` operation over a sequence of $N$ operations?" options=["$O(1)$","$O(\log N)$","$O(N)$","$O(N^2)$"] answer="$O(1)$" hint="Consider the total number of elements pushed and popped across the entire sequence of operations. Each element can be pushed once and popped once." solution="Step 1: Use the aggregate method for amortized analysis.
We want to find the total cost of a sequence of $N$ operations and then divide by $N$.

Step 2: Analyze the cost of `PUSH` and `MULTIPOP`.

• `PUSH(x)`: Adds one element. Cost is 1.


• `MULTIPOP(k)`: Removes up to $k$ elements. The cost is the number of elements actually popped.

Step 3: Determine the total maximum cost for $N$ operations.
Each element can be pushed onto the stack exactly once.
Each element can be popped from the stack exactly once.
Therefore, the total number of `PUSH` operations is at most $N$.
The total number of elements popped across all `MULTIPOP` operations cannot exceed the total number of elements pushed.
So, if there are $N$ operations in total, the maximum total cost for all `PUSH` operations is $N$. The maximum total cost for all `MULTIPOP` operations is also $N$ (since each element is popped at most once).

>

Step 4: Calculate the amortized cost.

>

Answer: The amortized cost of a `MULTIPOP` operation is $O(1)$."
:::

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Consider the following algorithm for finding the maximum element in an array $A$ of $N$ integers.
```
function FindMax(A, N):
if N == 0: return null
max_val = A[1]
for i from 2 to N:
if A[i] > max_val:
max_val = A[i]
return max_val
```
What is the best-case number of comparisons performed by this algorithm?" options=["1","$N-1$","$N$","$2N$"] answer="$N-1$" hint="The best case for this algorithm is not about early exit but about minimizing assignments to `max_val`. However, the number of comparisons remains constant for a given $N$." solution="Step 1: Analyze the operations.
The algorithm initializes `max_val` with `A[1]`.
The loop runs from $i=2$ to $N$, performing one comparison `A[i] > max_val` in each iteration.
This loop executes $N-1$ times.

Step 2: Determine best case.
The number of comparisons ($N-1$) is fixed regardless of the input array, as the loop always runs completely. The best case for this algorithm would be minimizing the number of assignments to `max_val`, which happens if the array is sorted in descending order (e.g., `[10, 9, 8, ..., 1]`). However, the question asks for comparisons, which is constant.

>

"
:::

:::question type="NAT" question="A binary search algorithm takes $O(\log N)$ time in the worst case. If we are searching for an element in a sorted array of $N$ elements, and the element is guaranteed to be present, what is the maximum number of comparisons (including the final equality check) required to find the element?" answer="floor(log2(N)) + 1" hint="In a binary search, each comparison halves the search space. The number of comparisons is related to the depth of the binary search tree." solution="Step 1: Understand binary search comparisons.
In binary search, each comparison eliminates half of the remaining search space. The maximum number of comparisons corresponds to traversing a path from the root to a leaf in a balanced binary search tree of $N$ nodes.

Step 2: Relate to tree height.
The height of a perfectly balanced binary tree with $N$ nodes is $\lfloor \log_2 N \rfloor$.
The number of comparisons is the number of nodes visited on the path from the root to the target element.
If the element is guaranteed to be found, it will be found at some depth. The maximum depth is $\lfloor \log_2 N \rfloor$.
A node at depth $d$ requires $d+1$ comparisons (including the comparison at the node itself).
The root is at depth 0. A leaf is at depth $\lfloor \log_2 N \rfloor$.

Step 3: Calculate maximum comparisons.
The maximum number of comparisons occurs when the element is found at a leaf node (maximum depth).
If $N=1$, $\lfloor \log_2 1 \rfloor + 1 = 0 + 1 = 1$.
If $N=2$, $\lfloor \log_2 2 \rfloor + 1 = 1 + 1 = 2$.
If $N=3$, $\lfloor \log_2 3 \rfloor + 1 = 1 + 1 = 2$. (e.g., for [1,2,3], search for 3: check 2, then check 3)
If $N=7$, $\lfloor \log_2 7 \rfloor + 1 = 2 + 1 = 3$.
If $N=8$, $\lfloor \log_2 8 \rfloor + 1 = 3 + 1 = 4$.

>

"
:::

:::question type="MCQ" question="Consider a queue implemented using a circular array of fixed size $M$. The `ENQUEUE` operation adds an element to the rear, and `DEQUEUE` removes from the front. If the queue is full, `ENQUEUE` fails. If the queue is empty, `DEQUEUE` fails. What is the worst-case time complexity for a single `ENQUEUE` operation?" options=["$O(1)$","$O(\log M)$","$O(M)$","$O(M^2)$"] answer="$O(1)$" hint="In a circular array implementation, `ENQUEUE` typically involves updating pointers and placing an element, which are constant time operations." solution="Step 1: Analyze the `ENQUEUE` operation in a circular array.
A circular array queue maintains `front` and `rear` pointers (or indices).
To `ENQUEUE`:

Check if the queue is full (e.g., `(rear + 1) % M == front`).

If not full, increment `rear` (modulo $M$).

Place the new element at `array[rear]`.

These operations (comparison, arithmetic, assignment) take constant time.

Step 2: Determine worst-case.
The worst case for `ENQUEUE` occurs when it has to check if the queue is full. This check is also a constant-time operation. No resizing or shifting of elements occurs in a fixed-size circular array.

>

"
:::

:::question type="MSQ" question="Which of the following statements about worst-case analysis are true?" options=["Worst-case analysis provides an upper bound on an algorithm's running time.","The worst-case input for an algorithm is always unique.","Worst-case analysis is useful for real-time systems where performance guarantees are critical.","An algorithm's worst-case time complexity can be better than its best-case time complexity."] answer="Worst-case analysis provides an upper bound on an algorithm's running time.,Worst-case analysis is useful for real-time systems where performance guarantees are critical." hint="Consider the definitions and applications of worst-case analysis. Think about scenarios where guarantees are paramount." solution="Option 1: Worst-case analysis provides an upper bound on an algorithm's running time.
✅ This is true by definition. The worst case describes the maximum time an algorithm will take for any input of a given size.

Option 2: The worst-case input for an algorithm is always unique.
❌ This is false. For many algorithms, multiple distinct inputs can trigger the worst-case behavior. For example, for linear search, if the element is not present, any array where the element is absent is a worst-case input.

Option 3: Worst-case analysis is useful for real-time systems where performance guarantees are critical.
✅ This is true. In real-time systems, it's crucial to know the absolute maximum time an operation might take to ensure deadlines are met. Average-case performance is insufficient here.

Option 4: An algorithm's worst-case time complexity can be better than its best-case time complexity.
❌ This is false. By definition, the worst case represents the maximum operations, while the best case represents the minimum operations. The worst-case complexity can never be 'better' (i.e., faster, or lower complexity class) than the best-case complexity.

>

>
>

"
:::

:::question type="MCQ" question="Consider a hash table using open addressing with linear probing. The table size is $M$. We want to insert $N$ distinct keys, where $N < M$. What is the average-case number of probes for an insertion, assuming simple uniform hashing and that the table is not full?" options=["$O(1)$","$O(\log M)$","$O(N)$","$O(M)$"] answer="$O(1)$" hint="For open addressing with linear probing, the average-case performance is usually expressed in terms of the load factor $\alpha = N/M$. When $\alpha$ is small (e.g., constant), the expected probes are constant." solution="Step 1: Define the load factor.
The load factor $\alpha = N/M$ represents the fraction of the hash table that is occupied.

Step 2: Analyze linear probing performance.
For open addressing with linear probing, the expected number of probes for an unsuccessful search (which is similar to an insertion, as it probes until an empty slot is found) is approximately $1/(1-\alpha)^2$.

Step 3: Evaluate average case for $N < M$.
Since $N < M$, the load factor $\alpha < 1$. If we consider a scenario where $N$ is much smaller than $M$ (e.g., $\alpha$ is a small constant like $0.5$), then $1/(1-\alpha)^2$ becomes a constant.
For example, if $\alpha = 0.5$, expected probes $\approx 1/(0.5)^2 = 4$.
Thus, for a constant load factor (i.e., $N$ is proportional to $M$), the average number of probes is constant.

>

"
:::

---

Summary

question type="MCQ" question="For a sorting algorithm that checks if an array is already sorted before performing any major sorting operations, what is the best-case time complexity if the input array is already sorted?" options=["$O(1)$","$O(\log n)$","$O(n)$","$O(n \log n)$"] answer="$O(n)$" hint="Checking if an array of size $n$ is sorted requires iterating through all elements once." solution="Step 1: Analyze the 'check sorted' operation. To verify if an array $A$ of size $n$ is sorted, we must iterate from $A[1]$ to $A[n-1]$ and check if $A[i] \le A[i+1]$ for all $i$. This takes $O(n)$ time.

Step 2: Determine the total complexity.
If the array is already sorted, the algorithm performs this $O(n)$ check and then terminates without further sorting.

>

"
:::

---

2. Worst Case Analysis

We define the worst case as the scenario where an algorithm performs the maximum number of operations for a given input size $n$. This provides an upper bound on the algorithm's runtime.

Worked Example 1: Linear Search

Consider the `LinearSearch(A, x)` algorithm.

Step 1: Identify the worst-case input

The worst case occurs when the target element $x$ is either at the last position of the array or not present in the array at all. The loop iterates through all $n$ elements.

>

Answer: The worst-case time complexity for Linear Search is $O(n)$.

Worked Example 2: Recursive Selection Algorithm (Inspired by PYQ 3 & 4)

Consider the `mystery` function which attempts to find the $k$-th smallest element in an array $A$.

```
function mystery(A, k) {
n = length(A);
if (k > n) return A[n];

v = A[1]; // Pivot is always the first element
AL = [ A[j] : 1 <= j <= n, A[j] < v ];
AV = [ A[j] : 1 <= j <= n, A[j] == v ];
AR = [ A[j] : 1 <= j <= n, A[j] > v ];

if (length(AL) >= k) return mystery(AL, k);
if (length(AL) + length(AV) > k) return v;
return mystery(AR, k - (length(AL) + length(AV)));
}
```

Step 1: Analyze the operations at each step.

At each recursive call, the algorithm scans the entire current array to partition it into `AL`, `AV`, and `AR`. This partitioning takes $O(m)$ time, where $m$ is the length of the current array.

Step 2: Identify the worst-case input for the pivot choice.

The worst case occurs when the pivot $v=A[1]$ is consistently chosen as the smallest or largest element in the array. This leads to highly unbalanced partitions.

Consider $A = [1, 2, 3, \dots, n]$ and we search for $k=n$.

• First call: $v=1$. `AL` is empty, `AV` contains `[1]`, `AR` contains `[2, 3, \dots, n]`.


• The recursive call is `mystery(AR, n-1)`, where `AR` has size $n-1$.


• This pattern continues, with the array size decreasing by only one element in each recursive call.

Step 3: Formulate the recurrence relation.

Let $T(n)$ be the time complexity for an input of size $n$. In the worst case, the partitioning takes $O(n)$ and the recursive call is made on an array of size $n-1$.

>

Step 4: Solve the recurrence relation.

>

Answer: The worst-case time complexity is $O(n^2)$. An example worst-case input is an already sorted array $A = [1, 2, \dots, n]$ searching for the $n$-th element, or a reverse-sorted array $A = [n, n-1, \dots, 1]$ searching for the 1st element.

:::question type="MCQ" question="Consider a search algorithm for an $n \times n$ matrix $A$ where each row and column is sorted in ascending order. The algorithm starts at $A[1,n]$ (top-right corner) and searches for $k$. If $A[i,j] = k$, it returns $(i,j)$. If $A[i,j] < k$, it moves down to $A[i+1,j]$. If $A[i,j] > k$, it moves left to $A[i,j-1]$. What is a worst-case input for this algorithm if $k$ is present?" options=["$k$ is at $A[1,1]$","$k$ is at $A[n,n]$","$k$ is at $A[1,n]$","$k$ is at $A[n,1]$"] answer="$k$ is at $A[n,1]$" hint="Analyze the movement pattern. To reach $A[n,1]$ from $A[1,n]$, the algorithm must traverse the maximum number of rows and columns." solution="Step 1: Understand the search strategy.
Starting at $(1,n)$:

• If current element is less than $k$, move down (increase row index).


• If current element is greater than $k$, move left (decrease column index).


• If current element equals $k$, found.

Step 2: Identify the path for maximum operations.
To maximize operations, the algorithm should be forced to traverse as many rows and columns as possible.

• To move down $n-1$ times, $k$ must be greater than or equal to elements in $A[1,j], A[2,j], \dots, A[n-1,j]$.


• To move left $n-1$ times, $k$ must be less than or equal to elements in $A[i,n], A[i,n-1], \dots, A[i,2]$.

Consider $k$ at $A[n,1]$.
The algorithm starts at $A[1,n]$. To reach $A[n,1]$, it must make $n-1$ 'down' moves and $n-1$ 'left' moves. This requires $2n-2$ comparisons in the worst case. For example, if all elements in the first column are less than $k$, it will move down until $A[n,n]$. Then, if $A[n,j] > k$ for $j > 1$, it will move left until $A[n,1]$. This path covers the maximum number of steps.

>

>

"
:::

---

3. Average Case Analysis

We define the average case as the expected number of operations for a given input size $n$, assuming a specific probability distribution over all possible inputs. This requires probabilistic analysis.

Worked Example: Linear Search (Average Case)

Consider `LinearSearch(A, x)` on an array $A$ of size $n$. We assume the following:

The element $x$ is present in the array with probability $p$.

If $x$ is present, it is equally likely to be at any of the $n$ positions (i.e., probability $1/n$ for each position).

If $x$ is not present (probability $1-p$), the algorithm performs $n$ comparisons.

Step 1: Calculate the expected number of comparisons if $x$ is present.

If $x$ is at position $i$, it takes $i$ comparisons.
The probability of $x$ being at position $i$ given it's present is $1/n$.

>

Step 2: Calculate the total average number of comparisons.

>

Answer: The average-case time complexity is $O(n)$. For $p=1$ (always present), it's $O(n/2) = O(n)$. For $p=0$ (never present), it's $O(n)$.

:::question type="NAT" question="A hash table uses chaining to resolve collisions. The load factor is $\alpha = N/M$, where $N$ is the number of items and $M$ is the number of slots. Assuming simple uniform hashing, what is the average number of probes (comparisons) for an unsuccessful search?" answer="alpha" hint="In simple uniform hashing, each item is equally likely to be hashed into any slot. An unsuccessful search must traverse the entire chain at the hashed slot." solution="Step 1: Understand simple uniform hashing and unsuccessful search.
Simple uniform hashing implies that any given item is equally likely to hash into any of the $M$ slots, independently of where other items hash.
For an unsuccessful search, we hash the key to a slot $j$. If slot $j$ has a chain of length $L_j$, we must traverse all $L_j$ elements in that chain to confirm the key is not present.

Step 2: Calculate the expected chain length.
The expected length of a chain at any given slot $j$ is the total number of items $N$ divided by the total number of slots $M$. This is the definition of the load factor $\alpha$.

>

Step 3: Determine the average probes.
Since an unsuccessful search must traverse the entire chain at its hashed slot, the average number of probes is equal to the average chain length.

>

"
:::

---

Advanced Applications

1. Concurrent Execution Outcomes

When multiple processes access and modify shared variables concurrently, the final state can depend on the interleaving of operations. We analyze best (minimum) and worst (maximum) possible outcomes by considering all valid execution schedules.

Worked Example: Shared Variable Update (Inspired by PYQ 1)

Consider two procedures, `proc1` and `proc2`, running in parallel. `x` is a shared variable initialized to $0$.

```c
int x = 0;

proc1 {
int temp1 = x;
x = temp1 + 1;
temp1 = x;
x = temp1 + 1;
}

proc2 {
int temp2 = x;
x = temp2 + 1;
}
```

Step 1: Analyze `proc1` operations without interference.

If `proc1` runs alone:

`temp1 = x;` (temp1 = 0)

`x = temp1 + 1;` (x = 1)

`temp1 = x;` (temp1 = 1)

`x = temp1 + 1;` (x = 2)

Final `x = 2`.

Step 2: Analyze `proc2` operations without interference.

If `proc2` runs alone:

`temp2 = x;` (temp2 = 0)

`x = temp2 + 1;` (x = 1)

Final `x = 1`.

Step 3: Identify the minimum possible value for `x`.

The minimum value occurs when `proc2`'s write operation, based on an old value of `x`, is the very last operation to complete, effectively overwriting any previous increments.

> Interleaving for Minimum `x = 1`:
>
> 1. `proc1`: `temp1 = x;` ($\text{temp1}=0$)
> 2. `proc2`: `temp2 = x;` ($\text{temp2}=0$)
> 3. `proc1`: `x = temp1 + 1;` ($x=1$)
> 4. `proc1`: `temp1 = x;` ($\text{temp1}=1$)
> 5. `proc1`: `x = temp1 + 1;` ($x=2$)
> 6. `proc2`: `x = temp2 + 1;` ($x=1$) // `proc2` writes 1, based on its initial read of 0. This is the last operation.

Step 4: Identify the maximum possible value for `x`.

The maximum value occurs when all increments are applied sequentially without any overwrites based on stale reads.

> Interleaving for Maximum `x = 3`:
>
> 1. `proc1` fully executes:
> - `temp1 = x;` ($\text{temp1}=0$)
> - `x = temp1 + 1;` ($x=1$)
> - `temp1 = x;` ($\text{temp1}=1$)
> - `x = temp1 + 1;` ($x=2$)
> 2. `proc2` fully executes:
> - `temp2 = x;` ($\text{temp2}=2$)
> - `x = temp2 + 1;` ($x=3$)

Answer: The possible values for $x$ are $1, 2, 3$.
Minimum possible value for `x` is $1$.
Maximum possible value for `x` is $3$.

:::question type="MCQ" question="Consider $x=0$. `procA` performs `x = x + 1; x = x + 1;`. `procB` performs `x = x + 1;`. Both run concurrently. Which of the following values are possible for $x$ after both processes halt?" options=["1","2","3","4"] answer="2,3" hint="Trace interleavings. Identify the minimum and maximum possible outcomes. A value of 1 implies one of the increments was completely lost, which is not possible with these operations." solution="Step 1: Analyze `procA` and `procB` independently.
`procA` intends to add 2 to $x$.
`procB` intends to add 1 to $x$.
Total intended increments: 3.

Step 2: Determine the minimum possible value.
The minimum value occurs if one process's final write is based on an old value.

• Start: $x=0$


• `procA`: `tempA1 = x;` ($\text{tempA1}=0$)


• `procA`: `x = tempA1 + 1;` ($x=1$)


• `procA`: `tempA2 = x;` ($\text{tempA2}=1$)


• `procB`: `tempB1 = x;` ($\text{tempB1}=1$)


• `procB`: `x = tempB1 + 1;` ($x=2$)


• `procA`: `x = tempA2 + 1;` ($x=2$) // `procA` writes 2, based on `tempA2=1`. This overwrites `procB`'s increment.

Final $x=2$.

Step 3: Determine the maximum possible value.
The maximum value occurs when all increments are applied sequentially without any overwrites based on stale reads.

• `procA` fully executes: $x \to 0 \to 1 \to 2$.


• Then `procB` executes: $x \to 2 \to 3$.

Final $x=3$.

Step 4: List all possible values.
The possible values are $2$ and $3$.

>

"
:::

2. Amortized Analysis

We use amortized analysis to analyze the performance of a sequence of operations, where a single operation might be expensive, but the average cost over a long sequence of operations is low. It provides a worst-case guarantee on the average performance per operation.

Worked Example: Dynamic Array (Vector) Append Operation

Consider a dynamic array that doubles its capacity when it runs out of space. Appending an element usually takes $O(1)$ time, but when a reallocation occurs, it takes $O(N)$ time, where $N$ is the current number of elements.

Step 1: Analyze the cost of a sequence of $N$ `append` operations.

Let's start with an empty array of capacity 1.

• `append(1)`: Cost 1 (copy 0 elements, add 1). Capacity 1 -> 2.


• `append(2)`: Cost 1 (add 1). Capacity 2.


• `append(3)`: Cost 3 (copy 2 elements, add 1). Capacity 2 -> 4.


• `append(4)`: Cost 1 (add 1). Capacity 4.


• `append(5)`: Cost 5 (copy 4 elements, add 1). Capacity 4 -> 8.

The total cost for $N$ appends involves $N$ constant-time insertions plus the cost of reallocations. A reallocation occurs when the array size reaches a power of 2 (e.g., 1, 2, 4, 8, ...). If we append $N$ elements, the total number of elements copied during reallocations is approximately $1+2+4+\dots+2^k$ where $2^k < N$. This sum is $2N-1$.

>

Step 2: Calculate the amortized cost.

The total cost for $N$ appends is $O(N)$.

>

Answer: The amortized time complexity of the `append` operation for a dynamic array is $O(1)$.

:::question type="MCQ" question="A stack supports `PUSH(x)` (cost 1) and `MULTIPOP(k)` (pops $k$ elements or until empty, cost $k$). What is the amortized cost of a `MULTIPOP` operation over a sequence of $N$ operations?" options=["$O(1)$","$O(\log N)$","$O(N)$","$O(N^2)$"] answer="$O(1)$" hint="Consider the total number of elements pushed and popped across the entire sequence of operations. Each element can be pushed once and popped once." solution="Step 1: Use the aggregate method for amortized analysis.
We want to find the total cost of a sequence of $N$ operations and then divide by $N$.

Step 2: Analyze the cost of `PUSH` and `MULTIPOP`.

• `PUSH(x)`: Adds one element. Cost is 1.


• `MULTIPOP(k)`: Removes up to $k$ elements. The cost is the number of elements actually popped.

Step 3: Determine the total maximum cost for $N$ operations.
Each element can be pushed onto the stack exactly once.
Each element can be popped from the stack exactly once.
Therefore, the total number of `PUSH` operations is at most $N$.
The total number of elements popped across all `MULTIPOP` operations cannot exceed the total number of elements pushed.
So, if there are $N$ operations in total, the maximum total cost for all `PUSH` operations is $N$. The maximum total cost for all `MULTIPOP` operations is also $N$ (since each element is popped at most once).

>

Step 4: Calculate the amortized cost.

>

Answer: The amortized cost of a `MULTIPOP` operation is $O(1)$."
:::

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Consider the following algorithm for finding the maximum element in an array $A$ of $N$ integers.
```
function FindMax(A, N):
if N == 0: return null
max_val = A[1]
for i from 2 to N:
if A[i] > max_val:
max_val = A[i]
return max_val
```
What is the best-case number of comparisons performed by this algorithm?" options=["1","$N-1$","$N$","$2N$"] answer="$N-1$" hint="The best case for this algorithm is not about early exit but about minimizing assignments to `max_val`. However, the number of comparisons remains constant for a given $N$." solution="Step 1: Analyze the operations.
The algorithm initializes `max_val` with `A[1]`.
The loop runs from $i=2$ to $N$, performing one comparison `A[i] > max_val` in each iteration.
This loop executes $N-1$ times.

Step 2: Determine best case.
The number of comparisons ($N-1$) is fixed regardless of the input array, as the loop always runs completely. The best case for this algorithm would be minimizing the number of assignments to `max_val`, which happens if the array is sorted in descending order (e.g., `[10, 9, 8, ..., 1]`). However, the question asks for comparisons, which is constant.

>

"
:::

:::question type="NAT" question="A binary search algorithm takes $O(\log N)$ time in the worst case. If we are searching for an element in a sorted array of $N$ elements, and the element is guaranteed to be present, what is the maximum number of comparisons (including the final equality check) required to find the element?" answer="floor(log2(N)) + 1" hint="In a binary search, each comparison halves the search space. The number of comparisons is related to the depth of the binary search tree." solution="Step 1: Understand binary search comparisons.
In binary search, each comparison eliminates half of the remaining search space. The maximum number of comparisons corresponds to traversing a path from the root to a leaf in a balanced binary search tree of $N$ nodes.

Step 2: Relate to tree height.
The height of a perfectly balanced binary tree with $N$ nodes is $\lfloor \log_2 N \rfloor$.
The number of comparisons is the number of nodes visited on the path from the root to the target element.
If the element is guaranteed to be found, it will be found at some depth. The maximum depth is $\lfloor \log_2 N \rfloor$.
A node at depth $d$ requires $d+1$ comparisons (including the comparison at the node itself).
The root is at depth 0. A leaf is at depth $\lfloor \log_2 N \rfloor$.

Step 3: Calculate maximum comparisons.
The maximum number of comparisons occurs when the element is found at a leaf node (maximum depth).
If $N=1$, $\lfloor \log_2 1 \rfloor + 1 = 0 + 1 = 1$.
If $N=2$, $\lfloor \log_2 2 \rfloor + 1 = 1 + 1 = 2$.
If $N=3$, $\lfloor \log_2 3 \rfloor + 1 = 1 + 1 = 2$. (e.g., for [1,2,3], search for 3: check 2, then check 3)
If $N=7$, $\lfloor \log_2 7 \rfloor + 1 = 2 + 1 = 3$.
If $N=8$, $\lfloor \log_2 8 \rfloor + 1 = 3 + 1 = 4$.

>

"
:::

:::question type="MCQ" question="Consider a queue implemented using a circular array of fixed size $M$. The `ENQUEUE` operation adds an element to the rear, and `DEQUEUE` removes from the front. If the queue is full, `ENQUEUE` fails. If the queue is empty, `DEQUEUE` fails. What is the worst-case time complexity for a single `ENQUEUE` operation?" options=["$O(1)$","$O(\log M)$","$O(M)$","$O(M^2)$"] answer="$O(1)$" hint="In a circular array implementation, `ENQUEUE` typically involves updating pointers and placing an element, which are constant time operations." solution="Step 1: Analyze the `ENQUEUE` operation in a circular array.
A circular array queue maintains `front` and `rear` pointers (or indices).
To `ENQUEUE`:

Check if the queue is full (e.g., `(rear + 1) % M == front`).

If not full, increment `rear` (modulo $M$).

Place the new element at `array[rear]`.

These operations (comparison, arithmetic, assignment) take constant time.

Step 2: Determine worst-case.
The worst case for `ENQUEUE` occurs when it has to check if the queue is full. This check is also a constant-time operation. No resizing or shifting of elements occurs in a fixed-size circular array.

>

"
:::

:::question type="MSQ" question="Which of the following statements about worst-case analysis are true?" options=["Worst-case analysis provides an upper bound on an algorithm's running time.","The worst-case input for an algorithm is always unique.","Worst-case analysis is useful for real-time systems where performance guarantees are critical.","An algorithm's worst-case time complexity can be better than its best-case time complexity."] answer="Worst-case analysis provides an upper bound on an algorithm's running time.,Worst-case analysis is useful for real-time systems where performance guarantees are critical." hint="Consider the definitions and applications of worst-case analysis. Think about scenarios where guarantees are paramount." solution="Option 1: Worst-case analysis provides an upper bound on an algorithm's running time.
✅ This is true by definition. The worst case describes the maximum time an algorithm will take for any input of a given size.

Option 2: The worst-case input for an algorithm is always unique.
❌ This is false. For many algorithms, multiple distinct inputs can trigger the worst-case behavior. For example, for linear search, if the element is not present, any array where the element is absent is a worst-case input.

Option 3: Worst-case analysis is useful for real-time systems where performance guarantees are critical.
✅ This is true. In real-time systems, it's crucial to know the absolute maximum time an operation might take to ensure deadlines are met. Average-case performance is insufficient here.

Option 4: An algorithm's worst-case time complexity can be better than its best-case time complexity.
❌ This is false. By definition, the worst case represents the maximum operations, while the best case represents the minimum operations. The worst-case complexity can never be 'better' (i.e., faster, or lower complexity class) than the best-case complexity.

>

>
>

"
:::

:::question type="MCQ" question="Consider a hash table using open addressing with linear probing. The table size is $M$. We want to insert $N$ distinct keys, where $N < M$. What is the average-case number of probes for an insertion, assuming simple uniform hashing and that the table is not full?" options=["$O(1)$","$O(\log M)$","$O(N)$","$O(M)$"] answer="$O(1)$" hint="For open addressing with linear probing, the average-case performance is usually expressed in terms of the load factor $\alpha = N/M$. When $\alpha$ is small (e.g., constant), the expected probes are constant." solution="Step 1: Define the load factor.
The load factor $\alpha = N/M$ represents the fraction of the hash table that is occupied.

Step 2: Analyze linear probing performance.
For open addressing with linear probing, the expected number of probes for an unsuccessful search (which is similar to an insertion, as it probes until an empty slot is found) is approximately $1/(1-\alpha)^2$.

Step 3: Evaluate average case for $N < M$.
Since $N < M$, the load factor $\alpha < 1$. If we consider a scenario where $N$ is much smaller than $M$ (e.g., $\alpha$ is a small constant like $0.5$), then $1/(1-\alpha)^2$ becomes a constant.
For example, if $\alpha = 0.5$, expected probes $\approx 1/(0.5)^2 = 4$.
Thus, for a constant load factor (i.e., $N$ is proportional to $M$), the average number of probes is constant.

>

"
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="What is the time complexity of the following Python function?" options=["$O(n)$","$O(n \log n)$","$O(n^2)$","$O(n^3)$"] answer="$O(n^2)$" hint="The inner loop's iterations depend on the outer loop's variable. Consider the sum of an arithmetic progression." solution="The outer loop runs $n$ times. The inner loop runs $i+1$ times for each $i$. The total number of operations is approximately $1 + 2 + \dots + n = \frac{n(n+1)}{2}$, which simplifies to $O(n^2)$."
```python
def example_func(n):
count = 0
for i in range(n):
for j in range(i + 1):
count += 1
return count
```
:::

:::question type="NAT" question="An algorithm processes an array of $n$ elements. It uses a fixed-size auxiliary stack of 10 elements and internally creates a copy of the input array. If $n=200$, how many units of space (approximately) does it use in total for both the copy and the stack? (Assume each element takes 1 unit of space)." answer="210" hint="Sum the space used by the copied array and the fixed-size stack." solution="The copied array uses $n$ units of space. The stack uses 10 units of space. Total space = $n + 10$. For $n=200$, total space = $200 + 10 = 210$ units."
:::

:::question type="MCQ" question="For a linear search algorithm on an unsorted array of $n$ elements, when does the best-case time complexity $O(1)$ occur?" options=["When the element is not present in the array","When the element is at the very end of the array","When the element is the first element in the array","When the array is sorted"] answer="When the element is the first element in the array" hint="Best case implies the minimum possible number of operations." solution="Linear search checks elements sequentially. If the target element is found at the very first position, only one comparison is needed, resulting in $O(1)$ time complexity."
:::

:::question type="MCQ" question="Which of the following functions represents the fastest growing time complexity for large $n$?" options=["$O(n \log n)$","$O(n^2)$","$O(2^n)$","$O(n)$"] answer="$O(2^n)$" hint="Compare the growth rates of logarithmic, linear, polynomial, and exponential functions." solution="For large $n$, exponential functions ($O(2^n)$) grow significantly faster than polynomial functions ($O(n^2)$, $O(n)$) or polylogarithmic functions ($O(n \log n)$). The order of growth from slowest to fastest among the options is $O(n)$, $O(n \log n)$, $O(n^2)$, $O(2^n)$."
:::

---

What's Next?