Asymptotic Analysis Practice Questions

The average-case running time $A(n)$ of an algorithm is always less than or equal to its worst-case running time $W(n)$. This means that $A(n)$ is asymptotically bounded above by $W(n)$. Therefore, $A(n)$ is $O(W(n))$. For example, in some algorithms like Bubble Sort, the average case can be equal to the worst case.

To determine the increasing order of asymptotic complexity, we compare the growth rates of the given functions. A common way to do this is to substitute a sufficiently large value for $n$. Let's choose $n = 2^{10} = 1024$.

1. $f_1(n) = 2^n = 2^{1024}$. This is an exponential function, which grows very fast.
2. $f_2(n) = n^{3/2} = (2^{10})^{3/2} = 2^{15}$. This is a polynomial function.
3. $f_3(n) = n \log_2 n = 2^{10} \log_2 (2^{10}) = 2^{10} \times 10 = 10 \times 2^{10}$. This is a log-linear function, which grows slower than polynomial.
4. $f_4(n) = n^{\log_2 n} = (2^{10})^{\log_2 (2^{10})} = (2^{10})^{10} = 2^{100}$. This function grows faster than polynomial but slower than exponential.

Comparing the values:
$f_3(n) = 10 \times 2^{10}$
$f_2(n) = 2^{15}$
$f_4(n) = 2^{100}$
$f_1(n) = 2^{1024}$

Thus, the increasing order of asymptotic complexity is $f_3, f_2, f_4, f_1$.

To determine when package B is preferred over package A, we need to find the smallest value of k for which the time taken by B is less than the time taken by A. Let n be the number of records, where $n = 10^k$.

Time for Package A: $T_A = 0.0001n^2$
Time for Package B: $T_B = 10n \log_{10} n$

We are looking for the smallest k such that $T_B < T_A$:
$10n \log_{10} n < 0.0001n^2$

Since n (the number of records) must be positive, we can divide both sides by 10n:
$\log_{10} n < 0.00001n$
$\log_{10} n < 10^{-5}n$

Now, substitute $n = 10^k$ into the inequality:
$\log_{10}(10^k) < 10^{-5}(10^k)$
$k < 10^{k-5}$

Let's test the integer values of k starting from the options to find the smallest one that satisfies this condition:

• If k = 5: $5 < 10^{5-5} \implies 5 < 10^0 \implies 5 < 1$. This is false.
• If k = 6: $6 < 10^{6-5} \implies 6 < 10^1 \implies 6 < 10$. This is true.

Since the condition is false for k=5 and true for k=6, the smallest integer value of k for which package B is preferred is 6.

To determine the asymptotic order, categorize the functions by their growth rates: $a = n^{1/3}$, $d = n \log^9 n$, $c = n^{1.75}$, $e = (1.0000001)^n$, and $b = e^n$.
Comparing the polynomials, $n^{1/3}$ grows slower than $n \log^9 n$, which grows slower than $n^{1.75}$ (since $\lim_{n \to \infty } \frac{\log^9 n}{n^{0.75}} = 0$).
Any polynomial grows strictly slower than any exponential function with a base $c > 1$.
Between the exponentials, $1.0000001^n$ grows slower than $e^n$ because $1.0000001 < e \approx 2.718$.
Therefore, the increasing asymptotic order is $n^{1/3} \prec n \log^9 n \prec n^{1.75} \prec 1.0000001^n \prec e^n$, which corresponds to $a, d, c, e, b$.

The function $f1(n)$ is a recursive implementation that follows the recurrence relation $T(n) = T(n-1) + T(n-2) + O(1)$. Because it recalculates subproblems without memoization, the branching factor leads to exponential growth, specifically $\Theta(2^n)$. In contrast, $f2(n)$ computes the same values iteratively using a loop that runs from $i=2$ to $n$. Inside this loop, it performs only constant time operations, resulting in linear complexity $\Theta(n)$. Therefore, the running times are $\Theta(2^n)$ and $\Theta(n)$.

To compare the asymptotic growth, we evaluate the functions $f(n)=2^{n}$, $g(n)=n!$, and $h(n)=n^{\log n}$. Taking the logarithm of $f(n)$ and $h(n)$ gives $\log(f(n)) = n \log 2$ and $\log(h(n)) = (\log n)^2$. Since $n$ grows faster than $(\log n)^2$, $f(n)$ grows faster than $h(n)$, thus $h(n) = O(f(n))$. Comparing $g(n) = n!$ and $f(n) = 2^n$, we know $n!$ exceeds $2^n$ for all $n \ge 4$, which implies $g(n) = \Omega(f(n))$. Therefore, the statements $h(n) = O(f(n))$ and $g(n) = \Omega(f(n))$ are correct.

To compute $b^n \pmod{m}$ efficiently, we use the method of binary exponentiation, also known as exponentiation by squaring. This algorithm relies on the binary representation of the exponent $n$, which contains $\lfloor \log_2 n \rfloor + 1$ bits. For each bit in the binary representation of $n$, the algorithm performs at most one squaring and one multiplication operation. Since the number of operations is proportional to the number of bits in $n$, the total complexity is logarithmic with respect to $n$. Therefore, the tightest upper bound on the number of multiplications required is $O(\log n)$.

To derive the given asymptotic notation, we consider the recurrence relation for the function.
The function is int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor(sqrt(n))) + n); }.
For the target answer $\Theta(\log_2 \log_2 n)$, the additive term $n$ must be effectively a constant, implying the question asks for the number of recursive calls or a scenario where the work per step is constant.
Thus, the recurrence relation is modeled as:
$T(n) = T(\lfloor\sqrt{n}\rfloor) + 1$
Let $n = 2^m$. Then $\lfloor\sqrt{n}\rfloor \approx \sqrt{n} = 2^{m/2}$.
Substituting this into the recurrence:
$T(2^m) = T(2^{m/2}) + 1$
Let $S(m) = T(2^m)$. The recurrence becomes:
$S(m) = S(m/2) + 1$
This is a standard recurrence relation that solves to $S(m) = \Theta(\log m)$.
Finally, substitute back $m = \log_2 n$:
$T(n) = \Theta(\log (\log_2 n)) = \Theta(\log_2 \log_2 n)$

The given function gcd(n,m) implements the Euclidean algorithm. In each recursive step, the larger number is replaced by the smaller number, and the smaller number is replaced by the remainder of their division.

Let the sequence of calls be $(n_0, m_0), (n_1, m_1), \ldots, (n_k, m_k)$.
Initially, $(n_0, m_0) = (n, m)$.
The function makes a recursive call gcd(m, n%m). So, $(n_1, m_1) = (m, n\%m)$.
In general, $(n_{i+1}, m_{i+1}) = (m_i, n_i\%m_i)$. This is the standard form of the Euclidean algorithm.

Lamé's theorem states that the number of steps (divisions or recursive calls) required by the Euclidean algorithm for inputs $(n, m)$ with $n \geq m$ is at most $5 \times (\text{number of digits of } m)$. More formally, the number of steps is $O(\log m)$.

Since $m \leq n$, the number of recursive calls is bounded by $O(\log n)$.
For a tight bound, consider the worst-case scenario, which occurs when $n$ and $m$ are consecutive Fibonacci numbers, say $n=F_k$ and $m=F_{k-1}$. In this case, the number of recursive calls is proportional to $k$. Since $F_k \approx \phi^k / \sqrt{5}$ (where $\phi$ is the golden ratio), we have $k \approx \log_\phi(F_k \sqrt{5})$. Thus, the number of calls is $\Theta(\log F_k)$, which is $\Theta(\log n)$.

Therefore, the number of recursive calls is $\Theta(\log n)$.

The final answer is $\boxed{A}$.

Binary search operates by repeatedly dividing the search space in half with each comparison. Let $k$ be the total number of steps required to reduce a sorted array of size $n$ to a single element. After $k$ steps, the size of the remaining search interval is $\frac{n}{2^k}$. Since the search concludes when the interval size is reduced to 1, we set $\frac{n}{2^k} = 1$, which simplifies to $2^k = n$. Solving for $k$ by taking the logarithm yields $k = \log_2 n$. Consequently, the time complexity is $O(\log_2 n)$.

The provided C code segment defines a function IsPrime(n) which checks if a number n is prime. The variable T(n) denotes the number of times the for loop is executed.

1. Analyze the Upper Bound (Big-O notation):
   The for loop iterates from i=2 up to sqrt(n). In the worst-case scenario, the loop completes all its iterations without finding any divisors of n. This happens when n is a prime number (or n=2, 3 where the loop does not run).
   If n is a prime number greater than 3, the loop will run for i = 2, 3, \ldots, \lfloor \sqrt{n} \rfloor.
   The number of iterations is \lfloor \sqrt{n} \rfloor - 2 + 1 = \lfloor \sqrt{n} \rfloor - 1.
   Since \lfloor \sqrt{n} \rfloor - 1 is less than or equal to \sqrt{n}, the upper bound on the number of loop executions is O(\sqrt{n}).

2. Analyze the Lower Bound (Big-Omega notation):
   The minimum number of times the loop is executed.

   • For n=2, 3, the loop condition i ≤ \sqrt{n} (i.e., 2 ≤ \sqrt{2} or 2 ≤ \sqrt{3}) is false, so the loop executes 0 times. However, for n ≥ 4, \sqrt{n} ≥ 2.
   • If n is an even number greater than or equal to 4 (e.g., n=4, 6, 8, \ldots), the loop starts with i=2. The condition n \% 2 == 0 will be true, printf is called, and the function returns 0. In this case, the loop executes exactly 1 time.
   • If n is a prime number (e.g., n=5, 7, 11, \ldots), the loop will execute \lfloor \sqrt{n} \rfloor - 1 times. For n=5, T(5) = \lfloor \sqrt{5} \rfloor - 1 = \lfloor 2.23 \rfloor - 1 = 2-1 = 1.
     Since for n ≥ 4, the loop executes at least once (T(n) ≥ 1), we can say that T(n) is bounded below by a constant.
     Therefore, T(n) = \Omega(1).

3. Conclusion:
   Combining both analyses, T(n)=O(\sqrt{n}) and T(n)=\Omega (1).

The final answer is $\boxed{C}$

The loop executes with $i$ taking values $\lfloor n/2 \rfloor, \lfloor n/4 \rfloor, \lfloor n/8 \rfloor, \dots$ until $i=0$. The variable $j$ accumulates these values:
$j = \sum_{k=1}^{\lfloor \log_2 n \rfloor} \lfloor \frac{n}{2^k} \rfloor$
Expanding this summation, we get $j = \lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor + \lfloor \frac{n}{8} \rfloor + \dots + 1$.
This expression is a finite geometric series bounded above by:
$j < n \left( \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots \right) = n \sum_{k=1}^{\infty } \left(\frac{1}{2}\right)^k$
Since the infinite geometric series $\sum_{k=1}^{\infty } (\frac{1}{2})^k$ converges to $1$, we have $j < n \cdot 1$.
Therefore, the asymptotic complexity is $Val(j) = \Theta(n)$.

The transitive closure of a binary relation on $n$ elements can be represented as an $n \times n$ adjacency matrix. The standard approach to compute this is the Floyd-Warshall algorithm, which determines all-pairs reachability in a directed graph. The algorithm employs three nested loops, each iterating $n$ times to update the path reachability matrix. This results in an algorithmic complexity of $O(n \cdot n \cdot n) = O(n^3)$. Therefore, the asymptotic notation for computing the transitive closure is $O(n^3)$.

The function $foo(n)$ recursively calls $foo(i)$ for all $i$ ranging from $0$ to $n-1$.
The space complexity is determined by the maximum depth of the recursion stack at any point during execution.
To compute $foo(n)$, the execution path must first enter $foo(n-1)$, then $foo(n-2)$, continuing down to the base case $foo(0)$.
This sequence creates a chain of nested calls with a maximum recursion depth of $n$.
Since each stack frame requires constant space, the total space complexity is proportional to the depth of the recursion tree, which is $O(n)$.

The recursive definition of the function is $foo(n) = \sum_{i=0}^{n-1} foo(i)$ for $n > 0$, with the base case $foo(0) = 1.0$. To compute $foo(n)$ efficiently using memoization, we must store the results of $foo(i)$ for all $0 \leq i < n$ to avoid redundant calculations. Consequently, the modified function requires an array or lookup table of size $n$ to store these computed values. Since the algorithm maintains a table of size $n$, the space complexity required is proportional to $n$. Therefore, the space complexity of the modified function is $O(n)$.

Given $g(n) = O(h(n))$ and $h(n) = O(g(n))$, we have $g(n) = \Theta(h(n))$.
Since $f(n) = O(g(n))$, by transitivity $f(n) = O(h(n))$, making option B true.
Because $f(n) = O(h(n))$ and $g(n) = O(h(n))$, their sum $f(n) + g(n) = O(h(n) + h(n)) = O(h(n))$, making option A true.
If $h(n) = O(f(n))$, then $g(n) = O(h(n)) = O(f(n))$, contradicting $g(n) \neq O(f(n))$, so C must be true.
Finally, $f(n) = O(g(n))$ implies $f(n)h(n) = O(g(n)h(n))$ by multiplying both sides by $h(n)$, so the statement $f(n)h(n) \neq O(g(n)h(n))$ is false.

The loop runs exactly $n$ times. In each iteration, if $A[i] == 1$, the constant time operation $counter++$ occurs, contributing a total of $\Theta(n)$ for all $1$s. If $A[i] == 0$, the function $f(counter)$ is called with complexity $\Theta(counter)$. Since the $counter$ variable resets to $0$ after each call to $f$, the sum of all $counter$ values processed by $f$ across the entire loop is equal to the total number of $1$s in the array, which is at most $n$. Therefore, the total work for all $f$ calls is $\Theta(\sum counter) = \Theta(m)$, where $m \le n$. The total complexity is $\Theta(n) + \Theta(m) = \Theta(n)$.

The recurrence relation for the given function is $T(n) = 2T(n-1) + c$ for $n > 1$, where $c$ represents the constant work performed at each call.
Expanding this relation yields $T(n) = 2(2T(n-2) + c) + c = 4T(n-2) + 2c + c$.
Following this pattern, after $k$ recursive steps, the expression becomes $T(n) = 2^k T(n-k) + c \sum_{i=0}^{k-1} 2^i$.
Setting $k = n-1$ and substituting the base case $T(1) = 1$, we get $T(n) = 2^{n-1} T(1) + c(2^{n-1} - 1)$.
This simplifies to $T(n) = 2^{n-1} + c(2^{n-1} - 1)$, which demonstrates that the time complexity is dominated by the exponential term, $O(2^n)$.

The input size for the natural number $n$ is $L = \lceil \log_2 n \rceil$ bits. Computing the cube root $\lfloor n^{1/3} \rfloor$ using binary search or Newton's method requires $O(L)$ iterations to converge. Each iteration involves arithmetic operations on $L$-bit numbers, which take $O(L^c)$ time for some constant $c \geq 1$ (e.g., using Karatsuba multiplication). Therefore, the total time complexity is $O(L \times L^c) = O(L^{k}) = O((\log n)^k)$ for some constant $k > 0$. Since $(\log n)^k$ grows strictly faster than any poly-log-log function $(\log \log n)^m$, the complexity is not $O((\log \log n)^m)$. This matches option C.

For Claim 1, $(n+k)^m = n^m(1+\frac{k}{n})^m$. Since $(1+\frac{k}{n})^m \to 1$ as $n \to \infty$, $(n+k)^m = \Theta(n^m)$, making it correct.
For Claim 2, $2^{n+1} = 2 \cdot 2^n$. By definition, $2 \cdot 2^n \le c \cdot 2^n$ holds for $c \ge 2$, so $2^{n+1} = O(2^n)$, making it correct.
For Claim 3, $2^{2n+1} = 2 \cdot (2^2)^n = 2 \cdot 4^n$. The ratio $\frac{2 \cdot 4^n}{2^n} = 2^{n+1}$ tends to $\infty$ as $n \to \infty$, so $2^{2n+1} \neq O(2^n)$, making it incorrect.
Therefore, only claims 1 and 2 are correct.