Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences
- Option : A
- Explanation : Applying Master’s Theorem cn > nln3 1 cn > n0 Now checking af(n/b) ≤ kf(n) for some k < 1 1*cm/3 ≤ kcn This is true for k > 1/3 Hence solution is Θ(n).
- Option : C
- Explanation : B must be preferred on A as 0.0001 n2 < 10 n log10 n ⇒ 10-5 n < log10n ⇒ 10-5 < log10n1/n ⇒ n 10-5 < log10n We know log10n = k ⇒ 10k = t ⇒ k > 10-5 10k ⇒ k > 10k-5 ⇒ k – 5 > 0 ⇒ k > 5 Then min k = 6
- Option : C
- Explanation : If B(n), XXA(n) and W(n) denote best case, average case and worst case time complexities of an algorithm P respectively then B(n) = O(A(n)), A(n) = O(W(n))
- Option : D
- Explanation : Let the three pegs be A,B and C, the goal is to move n pegs from A to C using peg B The following sequence of steps are executed recursively 1. move n – 1 discs from A to B. This leaves disc n alone on peg A ..... T(n – 1) 2. move disc n from A to C ..... 1 3. move n – 1 discs from B to C so they sit on disc n T(n – 1) So, T(n) = 2T(n – 1) + 1
- Option : B
- Explanation : Θ(n3)
So, this is in Θ(log n)
Hence Answer is (B)
The outer for-loop goes for
iterations. The
inner for-loop runs independent of the otuer loop. And for each inner iteration n/2 gets added to k.
∴ Answer = n/2 x # outer loops x #Inner loops per outer loop
# Inner loops = Θ(log n) [∵2 Θ(log n) = Θ(n)]
∴ Answer = 
