Q. \( T(n) = \left\{\begin{matrix} T(n-1) + n & n > 1 \\ 1 & n = 1 \end{matrix}\right. \)

1. T(n) = T(n-1) + n

2. = T(n-2) + (n-1) + n

3. = T(n-3) + (n-2) + (n-1) + n

4. This substitution is done iteratively for 'n' times

5. = T(1) + n + (n-1) + (n-2) + (n-3) + .. + 1

6. = \( \frac{n(n+1)}{2} \)

7. = O(n²)

Q. \( T(n) = \left\{\begin{matrix} T(n-1) + 1/n & n > 1 \\ 1 & n = 1 \end{matrix}\right. \)

1. T(n) = T(n-1) + 1/n

2. = T(n-2) + 1/(n-1) + 1/n

3. = T(n-3) + 1/(n-2) + 1/(n-1) + 1/n

4. This substitution is done iteratively for 'n' times

5. = T(1) + 1/2 + 1/3 + ... + 1/(n-3) + 1/(n-2) + 1/(n-1) + 1/n

6. Now we know that A series of the form: log n = 1 + 1/2 + 1/3 + ... + 1/(n-3) + 1/(n-2) + 1/(n-1) + 1/n

7. T(n) = O(log n)

Q. \( T(n) = \left\{\begin{matrix} T(n/2) + 1 & n > 1 \\ 1 & n = 1 \end{matrix}\right. \)

1. T(n) = T(n/2) + 1

2. = T(n/2²) + 1 + 1

3. = T(n/2³) + 1 + 1 + 1

4. This substitution is done iteratively for 'k' times

5. >= T(n/2^k) + 1 + 1 + 1 ... (k times)

6. Now we assume 2^k = n; k = log₂n

7. = T(1) + k

8. T(n) = log₂n (As T(1) = 1 and k = log₂n)

Q. \( T(n) = \left\{\begin{matrix} T(n-1) + log n & n > 1 \\ 1 & n = 1 \end{matrix}\right. \)

1. T(n) = T(n-1) + log n

2. = T(n-2) + log (n-1) + log n

3. = T(n-3) + log (n-2) + log (n-1) + log n

4. Repeating the above iteration '(n-1)' times

5. = T(1) + log 1 + log 2 + ... + log (n-2) + log (n-1) + log n

6. We know that the series log 1 + log 2 + ... + log (n-2) + log (n-1) + log n = n log n

7. = n log n

Ans . O(n log n)

Q. \( T(n) = \left\{\begin{matrix} 2T(n/2) + 2 & n > 1 \\ 1 & n = 1 \end{matrix}\right. \)

1. T(n) = 2T(n/2) + 2

2. = 2{2 T(n/2²) + 2} + 2

3. = 2² T(n/2²) + 2² + 2

4. = 2² {2 T(n/2³) + 2} + 2² + 2

5. = 2³ T(n/2³) + 2³ + 2² + 2

6. We know that the above series if repeated 'k' times we get

7. = 2^k T(n/2^k) + 2^k + 2^k-1 + ... + 2

8. The geometric series is 2^k + 2^k-1 + ... + 2 = \( \frac{2(2^k -1)}{(2 - 1)} \)

9. = 2^k T(1) + 2(n-1) (As 2^k = n)

10. = n + 2n - 1 (As 2^k = n)

Ans . O(n)

Q. \( T(n) = \left\{\begin{matrix} 8T(n/2) + n^2 & n > 1 \\ 1 & n = 1 \end{matrix}\right. \)

1. T(n) = 8T(n/2) + n²

2. = 8{8 T(n/2²) + (n/2)²} + n²

3. = 8² T(n/2²) + (n²/2²) + n²

4. = 8² {8 T(n/2³) + (n/2²)²} + (n²/2²) + n²

5. = 8³ T(n/2³) + (n²/2²)² + (n²/2²) + n²

6. We know that the above series if repeated 'k' times we get

7. = 8^k T(n/2^k) + (n²/2²)^k-1 + ... + (n²/2²)¹ + (n²/2²)⁰

8. 2^k = n; k = log₂ n

9. = \( (2^3)^k T(1) + n^2 [ \frac{1}{(2^2)^{k-1}} + ... + \frac{1}{(2^2)^{1}} + \frac{1}{(2^2)^{0}}] \)

10. This series is decreasing and the value is approx = 1 which is equal to the last term of the series; i.e. \( [ \frac{1}{(2^2)^{k-1}} + ... + \frac{1}{(2^2)^{1}} + \frac{1}{(2^2)^{0}}] \)

11. So, = \( n^3 + n^2[1] \)

Ans . O(n³)

Q. 2T(n/2) + n

1. From recurrence tree we assume, \( 2^k = n, k = log_2 n \)

2. T(n) = n * k

3. T(n) = \( n log_2 n \)

Ans . T(n) = \( n log_2 n \)

Q. T(n) = 5T(n/5) + n

1. From recurrence tree we assume, \( 5^k = n, k = log_5 n \)

2. T(n) = n * k

3. T(n) = \( n log_5 n \)

Ans . T(n) = \( n log_5 n \)

Q. T(n) = T(n/3) + T(2n/3) + n

1. From recurrence tree we make assumption, \( (3/2)^k = n \) so \( k = log_{3/2} n \)

2. \( T(n) = n log_{3/2} n \)

Ans . T(n) = \( n log_{3/2} n \)

Q. T(n) = T(n/5) + T(4n/5) + n

1. From recurrence tree we make assumption, \( (5/4)^k = n\) so \( k = log_{5/4} n \)

2. \( T(n) = n log_{5/4} n \)

Ans . \( T(n) = n log_{5/4} n \)

Q. T(n) = T(n/5) + T(3n/5) + n

1. From the recurrence tree, we get assumption as \( n = (5/4)^k\)

2. T(n) = \( \frac{4n}{5} + (\frac{4}{5})^2n + ... + (\frac{4}{5})^kn \)

3. = \( n[\frac{(4/5)(1-(4/5)^k)}{(1-4/5)}] \)

4. = \( n[\frac{(4/5)(1)}{(1/5)}] \)

Ans . T(n) = O(n)

Q. T(n) = 3T(n/4) + n²

1. From the recurrence tree n = (3/4)^k

2. T(n) = \( \frac{3n^2}{4} + (\frac{3}{4})^2n^2 + ... + (\frac{3}{4})^kn^2 \)

3. = \( n^2[ \frac{(3/4)(1 - (3/4)^k)}{(1/4)} ] \)

4. T(n) = O(n²)

Ans . T(n) = O(n²)

Since divide and conquer algorithms occur quite frequently and produce recursive equations for their run times, it is important to be able to solve recursive equations. For problems that have a fixed number of identical sized recursive pieces there is a much simpler method known as the master theorem that can be used to solve certain recursive equations almost "by inspection".

Master Theorem

The master theorem can be employed to solve recursive equations of the form

\( T(n) = a T(n/b) + f(n) \)

where a ≥ 1, b > 1, and f(n) is asymptotically positive. Intuitively for divide and conquer algorithms, this equation represents dividing the problem up into a subproblems of size n/b with a combine time of f(n). For example, for merge sort a = 2, b = 2, and f(n) = Θ(n). Note that floors and ceilings for n/b do not affect the asymptotic behavior or the results derived using the theorem.

If the recursion is in the form shown above, then the recurrence can be solved depending on one of three cases (which relate the dominance of the recursive term to the combine term):

Case 1

If

\( f(n) = O(n^{{log_b}^a - \epsilon}) \)

for some constant ε > 0, then the solution to the recurrence is given by

\( T(n) = \Theta(n^{{log_b}^a}) \)

In this case, f(n) is polynomially bounded above by \( n^{{log_b}^a} \) (which represents the run time of the recursive term), i.e. the recursive term dominates the run time.

Case 2

If

\( f(n) = \Theta(n^{{log_b}^a}) \)

then the solution to the recurrence is given by

\( T(n) = \Theta(n^{{log_b}^a} lg n) \)

In this case, f(n) is "equal" to \( n^{{log_b}^a} lg n\) , i.e. neither term dominates thus the extra term to get the bound.

Case 3

If

\( f(n) = \Omega(n^{{log_b}^a + \epsilon }) \)

for some constant ε > 0 AND if a f(n/b) ≤ c f(n) for some constant c < 1 and sufficiently large n (this additional constraint is known as the regularity condition), then the solution to the recurrence is given by

\( T(n) = \Theta(f(n))\)

In this case, f(n) is polynomially bounded below by \( n^{{log_b}^a} \) (which represents the run time of the recursive term) with the additional regularity condition, i.e. the combine term dominates the run time.

Thus in all three cases it is important to compute the recursive term run time \( n^{{log_b}^a} \) and compare it asymptotically to the combine term run time to determine which case holds. If the recursive equation satifies either case 1 or case 2, the solution can then be written by inspection. If the recursive equation satisfies case 3, then the regularity condition must be verified in order to write down the solution.

Note: There are gaps between the cases where the theorem cannot be applied (as well as recursive equations that do not fit the form required by the theorem exactly). In these cases, other techniques must be used which we will see next lecture.

Q. T(n) = 9T(n/3) + n

1. For this recurrence we have a = 9, b = 3, f(n) = n and we have that

2. \( n^{log_{b}a} = n^{log_{3}9} \)

3. = Θ (n²)

4. Since f(n) = O(\( n^{log_{3}{9 - \epsilon}} \) where ε = 1. Here we can apply Case 1: of Master's theorem and we get

Ans . T(n) = Θ(n²)

Q. T(n) = T(2n/3) + 1;

1. We have a = 1, b = 3/2, f(n) = 1 and we have

2. \( n^{log_{b}a} = n^{log_{3/2}1} = n^0 = 1\)

3. Since we have f(n) = Θ(\( n^{log_{b}a} = \Theta(1) \))

4. The solution we get is

Ans . T(n) = Θ(lg n)

Q. T(n) = 3T(n/4) + n lg n

1. We have a = 3, b = 4, f(n) = n lg n

2. \( n^{log_{b}a} = n^{log_{4}3} = O(n^{0.793}) \)

3. Since we have f(n) = Ω(\( n^{log_4{3+\epsilon}} \)) where ε = 0.2

4. We can show that case 3: applies here since af(n/b) ≤ cf(n) for c = 3/4. So we get

Ans . T(n) = Θ(n lg n)

Q. T(n) = 2T(n/2) + n lg n

1. We know that a = 2, b = 2, f(n) = n lg n and \( n^{log_b{a}} = n\)

2. f(n) = n lg n is asymptotically larger than \( n^{log_b{a}} = n\). But it is not polynomially large since the ratio \( \frac{f(n)}{n^{log_b{a}}} = \frac{n lg n}{n} = lg n\) is asymptotically less than \( n^{\epsilon} \) for any positive constant ε

Ans . Cant be solved using masters theorem

Q. T(n) = 2T(n/2) + Θ(n)

1. We have a = 2, b = 2 and f(n) = Θ(n) and we have

2. \( n^{log_b{a}} = n^{log_2{2}} = n\)

3. Case 2 of masters theorem applies since f(n) = Θ(n)

Ans . T(n) = Θ(n lg n)

Q. T(n) = 8T(n/2) + Θ(n²)

1. We have a = 8, b = 2, f(n) = Θ(n²)

2. \( n^{log_b{a}} = n^{log_2{8}} = n^3 \)

3. Since n³ is polynomially larger than f(n) i.e. f(n) = O(\( n^{3-\epsilon} \)) for ε = 1

4. Case 1: applies and we get T(n) = Θ(n³)

Ans . T(n) = Θ(n³)

Q. T(n) = 7T(n/2) + Θ(n²)

1. We have a = 7, b = 2, f(n) = Θ(n²)

2. \( n^{log_b{a}} = n^{log_2{7}} = n^{2.81} \)

3. Since f(n) = O(\( n^{lg 7 - \epsilon} \)) for ε = 0.8

4. Case 1: applies and we get T(n) = Θ(n^{lg 7})

Ans . T(n) = Θ(n^{lg 7})

Q. T(n) = 4T(n/2) + n²

1. We have a = 4, b = 2, f(n) = n²

2. \( n^{log_b{a}} = n^{log_2{4}} = n^{2} \)

3. Since f(n) = \( \Theta( n^{log_2{4}} )\)

4. Case 2: applies and we get T(n) = Θ(n² log n)

Ans . T(n) = Θ(n² log n)

Q. T(n) = 2ⁿT(n/2) + nⁿ

1. Since a is not a number, we cannot solve the recurrance using masters theorem.

Q. T(n) = 2T(n/2) + n / log n

1. We have a = 2, b = 2, f(n) = n / log n

2. \( n^{log_b{a}} = n^{log_2{2}} = n^{1} = n\)

3. Since difference of f(n) and \( n^{log_b{a}} \) is not polynomial we cannot solve recurrence using masters theorem

Q. T(n) = 0.5T(n/2) + n

1. We have a = 0.5, b = 2, f(n) = n

2. Since a < 1, we cannot solve recurrence using masters theorem

Q. T(n) = 64T(n/8) - n² log n

1. We have a = 64, b = 8, f(n) = - n² log n

2. Since the combination time i.e. f(n) = - n² log n is not positive, we cannot solve this recurrence using masters theorem

1. Probabilistic analysis is the use of probability in the analysis of problems. We use probabilistic analysis to study the running time of an algorithm.

Describe an implementation of the procedure RANDOM(a,b) that only makes calls to RANDOM(0,1). What is the expected running time of your procedure, as a function of a and b?

1. Algorithm 1: RANDOM(a,b)

2. n = lg(b - a + 1)

3. Initialize an array A of length n

4. while true do

5.    for i = 1 to n do

6.       A[i] = RANDOM(0, 1)

7.    end for

8.    if A holds the binary representation of one of the numbers in a through b then

9.        return number represented by A

10.    end if

11. end while

Each iteration of the while loop takes n time to run. The probability that the while loop stops on a given iteration is (b-a+1)/2ⁿ. Thus the expected running time is the expected number of times run times n. This is given by:

\( n\sum_{i \ge 1} i (1 - \frac{b-a+1}{2^n})^{i-1}(\frac{b-a+1}{2^n}) \)

\( n( \frac{b-a+1}{2^n})(\frac{2^n}{b-a+1})^2 \)

\( n(\frac{2^n}{b-a+1}) \)

O(lg(b-a)).

1. Scenario: You are using an employment agency to hire a new office assistant. The agency sends you one candidate each day. You interview the candidate and must immediately decide whether or not to hire that person. But if you hire, you must also fire your current office assistant —even if it’s someone you have recently hired.

2. Cost to interview is c_i per candidate (interview fee paid to agency). Cost to hire is c_h per candidate (includes cost to fire current office assistant + hiring fee paid to agency). Assume that c_h > c_i. You are committed to having hired, at all times, the best candidate seen so far. Meaning that whenever you interview a candidate who is better than your current office assistant, you must fire the current office assistant and hire the candidate. Since you must have someone hired at all times, you will always hire the first candidate that you interview.

3. Goal: Determine what the price of this strategy will be.

1. Pseudocode to model this scenario: Assumes that the candidates are numbered 1 to n and that after interviewing each candidate, we can determine if he is better than the current office assistant. Uses a dummy candidate '0' that is worse than all others, so that the first candidate is always hired.

1. HIRE-ASSISTANT(n)

2. best ← 0 ; candidate 0 is a least-qualified dummy candidate

3. for i ← 1 to n

4.     do interview candidate i

5.         if candidate i is better than candidate best

6.              then best ← i

7.                   hire candidate i

1. Cost: If n candidates, and we hire m of them, the cost is O(nc_i + mc_h)

2. Have to pay nc_i to interview, no matter how many we hire.

3. So we focus on analyzing the hiring cost mc_h. mc_h varies with each run i.e. —it depends on the order in which we interview the candidates.

4. This is a model of a common paradigm: we need to Þnd the maximum or minimum in a sequence by examining each element and maintaining a current “winner.” The variable m denotes how many times we change our notion of which element is currently winning.

Worst Case Analysis:

1. In the worst case, we hire all n candidates.

2. This happens if each one is better than all who came before. In other words, if the candidates appear in increasing order of quality.

3. If we hire all n, then the cost is O(nc_i + mc_h) = O(nc_h) (Since c_h > c_i)

Probabilistic analysis:

1. We have no control over the order in which candidates appear.So we could assume that they come in a random order:

2. The ordered list {rank(1), rank(2),...,rank(n)} is a permutation of the candidate numbers {1, 2,...,n}.

3. The list of ranks is equally likely to be any one of the n!permutations.

4. Equivalently, the ranks form a uniform random permutation: each of the possible n! permutations appears with equal probability.

Essential idea of probabilistic analysis:

1. We must use knowledge of, or make assumptions about, the distribution of inputs.

2. The expectation is over this distribution.

3. This technique requires that we can make a reasonable characterization of the input distribution.

Randomized algorithms:

1. We might not know the distribution of inputs, or we might not be able to model it computationally.

2. Instead, we use randomization within the algorithm in order to impose a distribution on the inputs.

For the hiring problem: Change the scenario:

1. The employment agency sends us a list of all 'n' candidates in advance.

2. On each day, we randomly choose a candidate from the list to interview (but considering only those we have not yet interviewed).

3. Instead of relying on the candidates being presented to us in a random order, we take control of the process and enforce a random order.

What makes an algorithm randomized: An algorithm is randomized if its behavior is determined in part by values produced by a random-number generator.

1. RANDOM(a, b) returns an integer r , where a ≤ r ≤ b and each of the b − a + 1 possible values of r is equally likely.

2. In practice, RANDOM is implemented by a pseudorandom-number generator, which is a deterministic method returning numbers that “look” random and pass statistical tests.

Q. Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?
T(n) = 2T(n/2) + Logn (GATE 2014 SET 2)

1. Θ(n)




2. Θ(nLogn)




3. Θ(n * n)




4. Θ(logn)

Ans . 1

1. solution
   By master's theorem
   a = 1,b=2 k =1
   therefore T(n) = Θ(n)

Q. The running time of an algorithm is represented by the following recurrence relation: (GATE 2009)

if n <= 3 then T(n) = n

else T(n) = T(n/3) + cn

$$

(A) θ(n)
(B) θ(nlogn)
(C) θ(n^2)
(D) θ(n^2log n)

Ans . A

T(n) = cn + T(n/3)
T(n)= cn + cn/3 + T(n/9)
T(n)= cn + cn/3 + cn/9 + T(n/27)
Taking the sum of infinite GP series. The value of T(n) will be less than this sum.
T(n) <= cn(1/(1-1/3))
<= 3cn/2
or we can say
cn <= T(n) <= 3cn/2
Therefore T(n) = Θ(n)

Q 2Which of the given options provides the increasing order of asymptotic complexity of functions f1,f2,f3 and f4?
f₁(n)=2ⁿ; f₂(n)=n^3/2 ; f₃(n)=nlog₂n ; f₄(n)=n^(log₂n)
(GATE 2011)

1. f3,f2,f4,f1




2. f3,f2,f1,f4




3. f2,f3,f1,f4




4. f2,f3,f4,f1

Ans . (A)

1. Let n=1024

2. f₁(n)=2¹⁰²⁴

3. f₂(n)=2¹⁵

4. f₃(n)=10 * 2¹⁰

5. f₄(n)=1024¹⁰=2¹⁰⁰

6. Therefore f₃ , f₂ , f₄ , f₁ is the required increasing order.

Q. Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 Which one of the following is FALSE? (GATE 2005)

1. T(n) = O((n²)




2. T(n) = Θ(n log n)




3. T(n) = Ω(n^2)




4. T(n) = O(n log n)

Ans . (c)

1. T(n) = 2T (n/2) + n ---eqn(a)

2. T(n/2)=2T(n/2²)+n/2 ---eqn(b)

3. Substitute (b) in (a)
   

4. T(n) = 2[2T(n/2²)+n/2]+n

5. = 2²T(n/2²)+2n

6. By generalizing,

7. T(n) = 2^kT(n/2^k)+kn ---eqn(c)

8. The base condition is T(1)=1,

9. so n/2^k = 1 then k=log n.

10. Substitute k=log n in eqn(c)

11. T(n) = nT(1)+(log n)n

12. = O(nlogn)

13. can also be written as O(n²)

14. Hence,Ω(n^2)

Q.5 Suppose there are ⌈log n⌉ sorted lists of ⌊n/log n⌋ elements each. The time complexity of producing a sorted list of all these elements is : (GATE 2005)

1. O(n log log n)




2. Θ(n log n)




3. Ω(n log n)




4. Ω(n³⁄₂)

Ans . (a)

1. We can merge x arrays of each size y in in O(xy*Logy) time using Min Heap.
   x = n/Logn
   y = Logn
   We get O(n/Logn * Logn * Log Log n) which is O(nLogLogn)
   

Common data for Q.6 and Q.7
Consider the following C-function:
double foo (int n)
{
int i;
double sum;
if (n = = 0) return 1.0;
else
{
sum = 0.0;
for (i = 0; i < n; i++)
sum += foo (i);
return sum;
}
}

Q.6 The space complexity of the above function is: (GATE 2005)

1. O(1)




2. O(n)




3. O(n!)




4. O(nⁿ)

Ans . (b)

1. The function foo() is recursive. Space complexity is O(n) as there can be at most O(n) active functions (function call frames) at a time.

Q.7 Suppose we modify the above function foo() and store the values of foo (i), 0 < = i < n, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be: (GATE 2005)

1. O(1)




2. O(n)




3. O(n!)




4. O(nⁿ)

Ans . (b)

1. Space complexity now is also O(n). We would need an array of size O(n). The space required for recursive calls would be O(1) as the values would be taken from stored array rather than making function calls again and again.

Q. The running time of an algorithm is represented by the following recurrence relation:

    if  n <= 3  then   T(n) = n
    else T(n) = T(n/3) + cn

Which one of the following represents the time complexity of the algorithm?

 (A) \theta(n) (B) \theta(n log n) (C) \theta(n^2) (D) \theta(n^2log n) 

(GATE 2009)

1. A




2. B




3. C




4. D

Ans: A

Previous

Next