Asymptotic complexity

Data for next three questions:

f n : There exist positive constant c and n0 such that
We know that O(g(n)) = .
0 ≤ f(n) ≤ c g(n), for all n ≥ n0
Given that𝑓 𝑛 = 10𝑛2 + 100 and 𝑔 𝑛 = 2𝑛 ; where n & n0 both are positive integers.
Q1. For which value of c& n0, 𝑓 𝑛 = 𝑂(𝑔(𝑛))?
(a) c = 1, n0 = 10 (b) c = 0.5, n0 = 12
(c) c = 1, n0 = 11 (d) Both b & c

Answer: d
Solution:
(I) f (n) = 10n2 + 100
g (n) = 2n
f (n) = 0 (g (n)) (given)
f (n) = c . g (n)
Checking option (a)
f (n) = 10  102 + 100 = 1100 [ n = 10]
g (n) = 210 = 1024 [ n = 10]
f (n) = 1 . g (n) [c=1]
11001024
Checking option (b)
c = 0.5, n0 = 12
f (n) = 10  (12)2 + 100 = 1540
g (n) = 212 = 4096
f (n)  c . g (n)
1540  0.5  4096
1540  2048 Correct;
Checking option (c)
c = 1, n = 11
f (n) = 10  (11)2 + 100 = 1210 + 100 = 1310
g (n) = 211 = 2048
f(n)  c . g(n)
1310  2048 Correct;

(ADA) Page 1
Q2. If c = 0.125 then for which value of n0, 𝑓 𝑛 = 𝑂(𝑔(𝑛))? ________

Answer: 15
Solution:
c = 0.125
f (n)  c. g(n)
10n2 + 100  0.125  (2n)
we need to check from n = 1 to 15
if n = 15
10  (15)2 + 100  0.125  215
2250 + 100  0.125  32768
2350  4096
Q3. If n0 = 9 then for which minimum value of c, 𝑓 𝑛 = 𝑂(𝑔(𝑛))? (Assume c is positive
integer)
(a) 10 (b) 5
(c) 2 (d) 1

Answer: c
Solution:
n0 = 9
f (n) = 10n2 + 100; g (n) = 2n
f (n) = 10  92 + 100 =910
g (n) = 29 = 512
min value for which
f (n)  c . g (n)
910  c. 512
1.77  c
Q4. The function f(n) = Ω(g(n)) if and only if there exist positive constants c, n0 such that
f(n) ≥ c.g(n), ∀n ≥ n0. Then which of the following statement is/are true?
(i) 10n2+ 4n + 2 = Ω (n2) with c =1 and n0 = 1
(ii) n3 –5n + 1 = Ω (n3) with c = 1 and n0 = 4
(iii) 2n2 + n log n + 1 = Ω (n2) with c =1 and n0 = 2
(iv) 6(2n) + 2n2 – 1 = Ω (2n+2) with c = 1 and n0 = 2
(a)i& ii only (b) ii, iii & iv only
(c)i, iii & iv only (d) All the above

Answer: c
Solution:
f (n) = Ω (g(n))
 f (n)  c. g (n)
(ADA) Page 2
 (i) 10n2+ 4n + 2 = Ω (n2)
10n2+ 4n + 2 = c. (n2) e = 1, n = 1
10 + 4 + 2  1 2

16  12  correct
(ii) n3 –5n + 1 = Ω (n3); c = 1 and n = 4
43 – 5  4 + 1 = 1  43
64 – 20 + 1  64
45  64
(iii) 2n2 + n log n + 1 = Ω (n2); c =1 and n = 2
2  22 + 2 log 2 + 1  c . 22
8 + 2 log 2 + 1  22
11  4;  correct
(iv) 6(2n) + 2n2 – 1 = Ω (2n+2); c = 1 and n = 2
64 + 8 – 1  1  24
71  16;  correct.
Q5. How many of the following expressions correctly describe f(n) = n2 + 10 n log(n)? ______
1. O(n3) 2.(n log n)
2
3.𝜃(n ) 4.o(n2logn)
5. 𝜔( 𝑛)
Answer: 5
Solution:
i. f (n) = O(n2) correct;  n2 > n log n correct.
ii. f (n) =  (n log n)  n2 > n log n correct.
iii. f (n) =  (n2) correct.
iv. f (n) = o(n2logn) = f (n) < c. n2 log n correct.
v. f (n) = 𝜔( 𝑛) = f (n) > c. 𝑛 correct.
Q6. How many of the following expressions correctly describe T(n)= 3 n+2? ______
1. O(32n)
2. O(n100)
3. O(nlog(n))
4. O((log(n))n)
5. 𝜃(30.5𝑛 )
6. O(30.5𝑛+100 )
1.5
7. ((3𝑛 ))
0.99
8. 𝜔(3𝑛 )

(ADA) Page 3
 Answer: option (1), (4) (8)
Solution:
T(n)= 3n+2
1. T (n) = O (32n)  (32 3n) < (3n 3n) correct.
2. T (n) = O (n100)  Growth of exponential is greater than growth of polynomial if
increase.
3. T (n) = O(nlog(n)) = 3n+2 > n log n incorrect or another method is take log on both side
(n + 2) log 3 > log n log n  option 3 is incorrect.
4. T (n) = O((log(n))n) = 3n + 2 taking log = n + 2 log2 3
(log n)n taking log n log log n
(n + 2) log2 3 < n log2 log n,  3n + 2 < (log n)n  correct.
5. 𝜃(30.5𝑛 ) = 3 n + 2 taking log (n + 2) log2 3
30.5n taking log n log2 3
(n + 2) log 3  n log2 3
𝑛
(n + 2) log 3  log2 3  incorrect.
2
6. O(3 0.5𝑛+100
) = 3n + 2 taking log (n + 2) log2 3
30.5 + 100 taking log (0.5 n + 100) log2 3
𝑛
3n + 2  O (32 + 100 )  incorrect.
3n + 2 =  (3n/2 + 100)
1.5 1.5 1.5
7. ((3𝑛 )) = 3n < 3𝑛 but T (n) = O (3𝑛 )
1.5
T (n)  ((3𝑛 ))  incorrect.
0.99 0.99
8. 𝜔(3𝑛 ) = 3n > 3 𝑛  correct.

Q7.
Let f(n) = 2n4 - 10n2 + 2n and g(n) = 𝑛6 + 2𝑛 + 2 𝑙𝑜𝑔𝑛. Which of the following is/are
true?
(i) f(n) + g(n) is O(n6) (ii) f(n) – g(n) is (n)
(iii) f(n) *g(n) is θ(n7) (iv) f(n) /g(n) is 𝑜(n1.25)
(a) i, ii & iii only (b) ii & iv only
(c) iii only (d) All the above

Answer: D
Solution:
f (n) = 2n4 – 10n2 + 2n = f (n) = O (n4)

g (n) = 𝑛6 + 2𝑛 + 2 log 𝑛 = g (n) = O(n3)

(i) f(n) + g(n) = O(n4) + O (n3) = O (n4) Correct

(ADA) Page 4
 (ii) f (n) – g(n) = O (n4) - O (n3) = O (n4) which is greater  correct.
(iii) f(n) *g(n) = θ(n7) = correct
𝑛4
(iv) f(n) /g(n) = 𝑜(n1.25) = = n < n1.25  correct.
𝑛3
Q8. 3 2
Consider the three functions:𝑓1 = 𝑛𝑘 , 𝑓2 = (log 𝑛)2𝑘 𝑎𝑛𝑑𝑓3 = 𝑘 𝑙𝑜𝑔 𝑘 (𝑛 ) ; where 0<k<1.
Which of the following statement is/are true?
I. 𝑓1 = 𝑂(𝑓2)
II. 𝑓2 = 𝑂 𝑓3
III.𝑓3 = 𝑂(𝑓1)
(a) I only (b) II only
(c) I & III only (d) none of these

Answer: b
Solution:
3 2
f1 = 𝑛𝑘 , f2 (logn)2k, f3 = 𝑘 𝑙𝑜𝑔 𝑘 (𝑛 )  𝑛2𝑙𝑜𝑔 𝑘 (𝑘) = n
taking log
k3 log n , 2k log2 log n, log n but 0 < k < 1
f3 > f1 > f2  f2 = O (f3) correct
f1  O (f2) because f1 > f2
f3  O (f1)  f3 > f1
Q9. Which of the following is not O (n3)?
(a) n+ 10000n (b) n2.9999
𝑛4
(c) 105n + 22.5𝑙𝑜𝑔 2 𝑛 (d)
𝑛 log 𝑛
Answer: d
Solution:
(a) n + 1000 n = O (n)  O (n3) correct.
(b) n2.999  O (n3) correct.
(c) 105n + 22.5𝑙𝑜𝑔 2 𝑛 = O (n2+5)  O (n3) correct
𝑛4 𝑛3
(d) = > n3 incorrect
𝑛 log 𝑛 𝑙𝑜𝑔𝑛
Q10. If 𝑓 𝑛 = (𝑛 ) then which of the following can be equivalent to 𝑓(𝑛)?
4

i. n2 + (log n)4
ii. ( 𝑛 + (log 𝑛)100 )7
iii. (1 + 0.00005)n
(a)i& iii only (b) iii only
(c) ii & iii only (d)none of the above

Answer: b
Solution:
f (n) = 𝜔 (n4) means f (n) > n4

(ADA) Page 5
 Growth of exponential functions are always greater than polynomial function.
Another method
n4 = 4 log n
(1.00005)n = n log 1.00005
 n log 1.00005 > 4 log n
 (1.00005)n > n4
Q11. If X = 𝑛 2𝑖
,. then X is equivalent to
𝑖=0 𝑛

(a)  (1) (b)  (log n)

(c)  (n) (d)  (n log n)

Answer: c
Solution:
2 2𝑖
X= 𝑖=0 𝑛
2 2 ×2 2 ×3 2 ×4 2𝑛
= + + + + . . .+
𝑛 𝑛 𝑛 𝑛 𝑛
2
= [ 1 + 2 + 3 + 4 + . . . n]
𝑛
2 𝑛 (𝑛+1)
= [ ] sum of A.P
𝑛 2
= (n + 1)
=  (n)
𝑛
Q12. If Y= 𝑛
𝑖=1 2𝑖 , then X is equivalent to
(a)  (1) (b)  (log n)
(c)  (n) (d)  (n log n)

Answer: D
Solution:
𝑛
Y= 𝑛𝑖=1
2𝑖
𝑛 1 1 1 1
= [ + + +... ]
2 1 2 3 𝑛
𝑛 𝑛 1
= log n  𝑖=1 𝑖 = log n
2
=  (n log n)
Q13. Which of the following represents the asymptotic growth of the expression 𝑛
𝑖=1 𝑖. 3
𝑖
?
(a) (3n+1) (b) (n.3nlogn)
(c) (3nlogn) (d) (n.3n+1)

Answer: D
Solution:
= 𝑛𝑖=1 𝑖. 3𝑖

(ADA) Page 6
 X = 1.3 + 2.32 + 3.33 + . . . + n.3n
- 3x = 32 + 2.33 + . . .+ (n – 1) 3n – n. 3n + 1
-2x = 3 + 32 + 33 + . . . + 3n – n 3n + 1
2x = n 3n + 1 – 3 (3n – 1)
𝑛 3
x = 3n + 1 - ( 3n – 1)   (n.3n+1)
2 4
Q14. How many of the following statement is/are true? ________
(i) 10 𝑛 + log n = O(n) (ii) 𝑛 + log n = O(log n)
(iii) 𝑛 + log n = 𝜃(n) (iv) 𝑛 + log n = 𝜃(log n)
(v) 𝑛 + log n = 𝜃( 𝑛) (vi) 𝑛 + log n = 𝜃(n)
(vii) 𝑛 + log n = 𝜔(n) (viii) 𝑛 + log n = 𝜔(log n)
(ix) 𝑛 + log n = 𝜔(1)

Answer: iv
Solution:
i. 10 𝑛 + log n = O(n) correct  𝑛 < n
ii. 𝑛 + log n = O(log n) incorrect 𝑛 > log n
iii. 𝑛 + log n = 𝜃(n) incorrect it should be O (n) or  ( log n)
iv. 𝑛 + log n = 𝜃(log n) incorrect it should be O (n) or  ( 𝑛)
v. 𝑛 + log n = 𝜃( 𝑛) correct
vi. 𝑛 + log n = 𝜃(n) incorrect it should be O (n)
vii. 𝑛 + log n = 𝜔(n) incorrect it should be O (n)
viii. 𝑛 + log n = 𝜔(log n) correct 𝑛 > log n
ix. 𝑛 + log n = 𝜔(1) correct

Q15. Which of the following statement is/are true?

1. There does not exist a pair of functions𝑓 𝑛 𝑎𝑛𝑑𝑔 𝑛 such that 𝑓 𝑛 ≤ 𝑂 𝑔 𝑛 and
𝑓 𝑛 ≥ 𝑔 𝑛 .
2. 𝑛2 log10 𝑛 ≤ 𝑂(𝑛2.12 )
3. 22𝑛 ≤ 𝑂 2𝑛
(a) 1 only (b) 1 & 2 only
(c) 2 only (d) All the above

Answer: c
Solution:
i. f (n) = n2 + 5n + 9
g (n) = n2
f (n) < O (g (n)) & f (n)   (g (n))  f (n) = (g (n))
ii. n2 log10n  n2.12
n2log10 < n2 n0.12
n0.12 > log10 n  true.
(ADA) Page 7
 iii. 22𝑛 ≤ 𝑂 2𝑛
2n. 2n  2n  false.

Q16. Which of the following statement is/are true?

1. If 𝑓 𝑛 = 𝑂 𝑔 𝑛 and𝑔 𝑛 = 𝑂 𝑕 𝑛 , 𝑡𝑕𝑒𝑛𝑓 𝑛 = 𝑂 𝑕 𝑛
2. If 𝑓 𝑛 = 𝜃 𝑔 𝑛 and𝑔 𝑛 = 𝜃 𝑕 𝑛 , 𝑡𝑕𝑒𝑛𝑓 𝑛 = 𝜃 𝑕 𝑛
3. If 𝑓 𝑛 =  𝑔 𝑛 and𝑔 𝑛 =  𝑕 𝑛 , 𝑡𝑕𝑒𝑛𝑓 𝑛 =  𝑕 𝑛
(a) 1 only (b) 1 & 2 only
(c) 1, 2 & 3 (d) None of these

Answer: c
Solution:
1. If 𝑓 𝑛 = 𝑂 𝑔 𝑛 and𝑔 𝑛 = 𝑂 𝑕 𝑛
f (n) = n5, g (n) = n6
h (n) = n7
f (n) = O (h (n))  true,
2. 𝑓 𝑛 = 𝜃 𝑔 𝑛 , 𝑔 𝑛 = 𝜃 𝑕 𝑛 ,
f (n) = n2 + 2n
g (n) = n2 + 1
h (n) = n2
f (n) = 𝜃 𝑔 𝑛 = 𝜃 𝑕 𝑛 ,  true.

Q17. Which of the following is tightest asymptotic bounds for the following definitions of
f (n). g(n) = (n2) and f (n) = g(n)2 + n4⇒ f (n) = ?
(a) O(n3) (b) Θ(n2)
(c) (n) (d) (1)

Answer: c
Solution:
f (n). g (n) = (n2)
f (n) = (g (n))2 + n4
f (n) =  (n)
g (n) =  (n) [It can be a possible case]
might because than f (n) = n4 and g (n) = n2
f (n) = (n2)2 + n4 = n4
f (n) might be equal to n4 or greater than n4
that means f (n) =  (1)

(ADA) Page 8
Q18. 20 20
20 20
Let𝑓 𝑛 = log log log 𝑛and g(n) =20 then which of the following is/are true?
i. f(n) = θ(g(n) ii.f(n) = (g(n)
iii. f(n) = O(g(n) iv. f(n) =  (g(n))
(a) i, ii & iii only (b) ii, iii & iv only
(c) ii & iv only (d) iv only
Answer: c
Solution:
i. f(n) = log log log 𝑛
20 20
ii. g (n) = 2020
f (n) =  (g (n)) because g (n) is constant & f (n) is depending on 2.
iii. f(n)  O (g (n)) f (n) is greater than g (n)
iv. f (n) =  (g (n)) f (n) > g (n) correct.
Q19. If f(n) is O(g(n)) and g(n) is O(h(n)), how many of the following is/are correct? _______
i. f(n) * g(n) is Θ(f(n) + g(n))
ii. f(n) + g(n) is O(max(g(n), h(n)) )
iii. f(n) is O(h(n))
iv. h(n) is O(f(n))
v.|f(n) – g(n)| is O(h(n))
𝑓 𝑛
vi. = 𝑜(𝑕(𝑛))
𝑔 𝑛

Answer: 3
Solution:
f (n) = O (g(n)) f (n) = n
g (n) = O (h (n)) g (O/2) = n2 + 4
h (n) = n3 + n2 + n
i. f(n) * g(n) is Θ(f(n) + g(n))
n (n2 + 4) =  (n3)
 (n3)   (n2)
n + n2 + 4 =  (n2) incorrect.
ii. f(n) + g(n) is O(max(g(n), h(n)) ) true
iii. f(n) = O(h(n)) true,
n = O (n3 + n2 + n)
n = O (n3)
iv. h(n) is O(f(n)) false
h (n) =  (f (n)) or  (f (n))
v. |f(n) – g(n)| = O(h(n)) false
𝑓 𝑛
vi. = 𝑜(𝑕(𝑛))
𝑔 𝑛

(ADA) Page 9
 𝑛 1
= = = O (f (n))
𝑛 2+ 4 𝑛
but if h (n) = O (1)
g (n) = O (n)
 f (n) =  (n) = g (n)
𝑓 𝑛
 = constant = O (h (n)) not always true.
𝑔 𝑛
Q20. Arrange the following function in increasing order of their asymptotic growth:
𝑓1 = 3𝑛3 + 𝑛 log 𝑛 2 , 𝑓2 = 2𝑛 ,
𝑓3 = (log 𝑛)10 , 𝑓4 = 𝑛!,
𝑓5 = 𝑛/𝑙𝑜𝑔𝑛, 𝑓6 = 𝑛
(a) 𝑓6, 𝑓5, 𝑓3, 𝑓1, 𝑓2, 𝑓4 (b)𝑓3, 𝑓6, 𝑓5, 𝑓1, 𝑓2, 𝑓4
(c)𝑓6, 𝑓3, 𝑓5, 𝑓1, 𝑓2, 𝑓4 (d)𝑓3, 𝑓5, 𝑓6, 𝑓1, 𝑓2, 𝑓4

Q21. Arrange the following functions in the ascending order of the growth rate.
n ,
f1(n) = nlog n log log(n!), 𝑓2(n) =
log 10 n
n
f3(n)=n100(logn)500, 𝑓4 n = ,
logn
f5(n)=nn+0.5log n f6(n)=2((logn)2) ,
f7(n)=n1.25, f8(n)=log(n50) ,
f9(n)=n51.
(a) f8, f6, f4, f2, f1, f7, f9, f3, f5 (b)f6, f8, f4, f2, f1, f7, f9, f3, f5
(c) f2, f8, f6, f4, f1, f7, f9, f3, f5 (d)f2, f6, f8, f4, f1, f7, f9, f3, f5

Q22. Arrange the following functions in the ascending order of the growth rate.
𝑛
g1(n) = 𝑛(1+0.005) , g2(n) = n(logn)4,
g3(n) = nlogn , g4(n) = nloglog n ,
log 𝑛 𝑙𝑜𝑔𝑛
g5(n) = log(n2n), g6(n) = 2 ,
𝑛2
g7(n) = 𝑒 𝑒 g8(n) = 3loglogn
(a) g5, g3, g2, g8, g6, g4, g1, g7 (b) g5, g3, g2, g6, g8, g4, g1, g7
(c) g3, g5, g2, g6, g8, g4, g1, g7 (d) g5,g3, g2, g6, g4, g8, g1, g7
Q23. Arrange the following functions in the non-decreasing order of the growth rate.
f1(n) = (2 + .5𝑛) 𝑛𝜋 f2(n) = 𝜋 1.05𝑛
𝑛
f3(n) = 4
f4(n) = 𝑛 2 𝑛

𝑛 2
f5(n) = 𝑛−1 f6(n) = 9log 729 𝑛
2 𝑛
f7(n) = 𝑛5(𝑙𝑜𝑔𝑛 ) f8(n) = n4 𝑛−3
(a)f6<f3<f5<f7<f8<f4<f2<f1 (b) f5=f3<f6<f7<f8<f4<f2<f1
(c) f6<f5=f3<f7<f8<f4<f2<f1 (d) none of these

(ADA) Page 10
 Answer: c
Solution:
𝑛
f1(n) = (2 + 0.5𝑛) 𝑛𝜋 taking log nlog
2

f2(n) = 𝜋 1.05𝑛 taking log 1.05n log .

f1 (n) > f2 (n)
(𝑛−2)
f3(n) = 𝑛
4
= 𝑛 𝑛−1 (𝑛 − 3) =  (n2)
4!

f3> f1 > f2

f4(n) = 𝑛 2 𝑛

Q24. Which of the following is/are true?

1. If f(n) = (g(n)) and g(n) = (f(n)), then f(n) = θ(g(n)).
2. If f(n) = o(g(n)), then g(n)  O(f(n)).
3. If f(n) = O(h(n)) and g(n) = O(h(n)), then f(n) + g(n) = O(h(n))
4. If f(n) = O(h(n)) and g(n) = O(h(n)), then f(n) . g(n) = O(h(n))
(a) Only 4 (b) Only 1 & 3
(c) Only 1, 2 & 3 (d) Only 2 & 4

Answer: c
solution:
f(n) = (g(n)) and g(n) = (f(n))
f (n) = n2 + n + 1 g (n) = n2
f (n) =  (g (n))  true;
f(n) = o(g(n)),
f (n) = n
g (n) = n2
g (n)  O (f(n))
g (n)  c.(f (n))  true
f(n) = O(h(n)) and g(n) = O(h(n)),
f (n) = n2; g (n) = n3; h (n) = n3
n2 + n3 =  (n3) = O (h (n)) true
f(n) = O(h(n)) and g(n) = O(h(n)),
f (n) . g (n) = O (h (n))
n2. n3 = O (n5)  O (h (n))
Q25. Arrange the following functions in the ascending order of their growth rate:
6𝑛
2 𝑛1.44 , , 8n + 𝑛 , 16 log n2, 𝑛2.24
𝑙𝑜𝑔𝑛

(ADA) Page 11
 6𝑛
(a) 16 log n2, , 8n + 𝑛 ,2 𝑛1.44 , 𝑛2.24
𝑙𝑜𝑔𝑛
6𝑛
(b) , 8n + 𝑛 , 16 log n2, 2 𝑛1.44 , 𝑛2.24
𝑙𝑜𝑔𝑛
6𝑛
(c) , 8n + 𝑛 , 16 log n2, 2 𝑛1.44 , 𝑛2.24
𝑙𝑜𝑔𝑛
6𝑛
(d) 16 log n2,2 𝑛1.44 , , 8n + 𝑛 , 𝑛2.24
𝑙𝑜𝑔𝑛

Answer: d
Solution:
f1 = 16 log n2 = 32 log n
log 𝑛
f2 = 2  𝑛 2 = 2  n0.72
6𝑛
f3 = = f1 < f2 < f3 < f4< f5
𝑙𝑜𝑔𝑛

f4 = 3n + 𝑛 = O (n)
f5 = n2.24/2 = n1.12
Q26. Arrange the following functions in the ascending order of their growth rate: (Take base of
log = 2) 6n3, nlog6n, n3/2, 8n2.25, (log2n)n, √n, 82n log n , n!
(a) √n, nlog6n, n3/2, 8n2.25, 6n3, (log2n)n, 82n log n , n!
(b) √n, nlog6n, n3/2, 8n2.25, 6n3, (log2n)n, n!, 82n log n
(c)(log2n)n, √n, nlog6n, n3/2, 8n2.25, 6n3, (log2n)n, n!, 82n log n
(d)√n, nlog6n, n3/2, 8n2.25, 6n3, 82n log n ,(log2n)n, n!
Answer: b
Solution:
6n3, nlog6n, n3/2, 8n2.25, (log2n)n, 𝑛 , 82n log n , n!
We know that
= 𝑛 < n3/2 < 8n2.25 < 6n3 < n! - - - - - - - (1)
and 𝑛 < n log n < n3/2 ( 𝑛 > log n) - - - -(2)
2𝑛
Now 82nlogn = 8log 2 𝑛 = (𝑛2𝑛 )log 2 8
= (n2n)3 = (nn)6 > n6
 82nlogn > n! - - - - - -(3)
Comparing 6n3, ( log 2 𝑛)1, n!
After taking log
log 6n3 = 3 log 2 6𝑛
log (log 2 𝑛)n = n log log n
log (n!)  log (nn)  n log n
 6n3 < (log 2 𝑛)n < n! - - - - -(4)
from (1), (2), (3), (4) we can say that
3
𝑛 < nlog 6 𝑛 < 𝑛2 < 8 𝑛2.25 < (log 2 𝑛)n < n! < 82nlogn

(ADA) Page 12
Q27. Arrange the following functions in the ascending order of the growth rate.
f1(n)= log 𝑙𝑜𝑔∗ 𝑛 f2(n) =log(𝑛𝑙𝑜𝑔𝑛)2 ,
f3(n)= 𝑛𝑛/ log log 𝑛 , f4(n) = ( 𝑛)𝑙𝑜𝑔𝑛 ,
f5(n) = (𝑙𝑜𝑔𝑛) 𝑙𝑜𝑔𝑛 , f6(n) = 4 𝑙𝑜𝑔𝑛𝑙𝑜𝑔𝑙𝑜𝑔𝑛 ,
2
f7(n) = (1+ )n
𝑛
(a) f7, f1, f2, f6, f5, f4, f3 (b) f1, f7, f2, f6, f5, f4, f3
(c) f7, f1, f6, f2, f5, f4, f3 (d) Both a & b

Answer: d
Solution:
f1 (n) = log log*n
f2(n) =log(𝑛𝑙𝑜𝑔𝑛)2
f1 < f2 because log* means log log …..logn
𝑛
𝑛
f3 (n) = 𝑛log 𝑙𝑜𝑔𝑛 taking log logn
𝑙𝑜𝑔𝑙𝑜𝑔𝑛
means f3 > f2> f1
1
f4 (n) = ( 𝑛)logn (taking log) (logn)2
2
f3 > f4 > f5 >f2 > f1
f5 (n) = (𝑙𝑜𝑔𝑛) 𝑙𝑜𝑔𝑛 taking log 𝑙𝑜𝑔𝑛 log2 log n
f3 > f4 > f5 > f2> f1
f6 = 4 𝑙𝑜𝑔𝑛𝑙𝑜𝑔𝑙𝑜𝑔𝑛 taking logn log logn
logn log logn
2
f7 (n) = (1+ )n taking log
𝑛
2
n log (1 + )
𝑛
f1 & f7 are constants.

Q28. Arrange the following functions in the non-decreasing order of the growth rate.
𝑓1 = 𝑛log log 𝑛 , 𝑓2 = 𝑛log 𝑛 ,
𝑓3 = (log 𝑛)log 𝑛 , 𝑓4 = (log 𝑛)𝑛! ,
𝑓5 = (𝑛!)log 𝑛 , 𝑓6 = (𝑛)log ⁡(𝑛!)
(a)f3, f1, f2, f6, f5, f4 (b) f1, f3, f2, f5, f6, f4
(c)f3, f1, f2, f5, f6, f4 (d) All of these
Answer:d
Solution:
f3  f1 = 𝑛log log 𝑛 < 𝑓2 = 𝑛log 𝑛
𝑓4 = (log 𝑛)𝑛! 𝑓5 = (𝑛!)log 𝑛 taking log
n! log log n log n log n! = n log n . log n
n nlog log n
n

𝑓6 = (𝑛)log ⁡(𝑛!) taking log

(ADA) Page 13
 log n! log n = n (log n)2
f 5  f6
Q29. Which of the following is/are true?
(i) 2n = (n!) (ii) 3log2n =  (n)
(iii) 3n= 2O(n) (iv) n2 = O(n log2n)
(a) i& iii only (b) ii & iii only
(c) iii only (d) none of the above

Answer: d
Solution:
(i) 2n = (n!)  false nn > 2n
(ii) 3log2n =  (n)
1 1
log 2 𝑛 = n log 2 3   ( 𝑛)
3 2
(iii) 3  2
n
 false
O(n)

iv) n = O(n log2n)  false

2

Only option (i) exists.

Q30. Arrange following function in the ascending order of growth rate
(i) n2, (ii)log10 n,
(iii) n log2n, (iv) nln n,
(v) (ln n)n, (vi) ln(nn),
ln n
(vii) (ln n) , (viii) (ln n)lnln n,
(ix)(lnln n)ln n, (x)3n/2
(a)ii, viii, iii, vi, i, ix, vii, iv, x, v (b) viii, ii, i, iii, vi, ix, vii, iv, v, x
(c)ii, ix, viii, vii, iv, v, vi, iii, i, x (d) viii, ii, iii, vi, i, ix, vii, iv, x, v

Answer: A
Solution:
n2 > log n
n2 > n log n > log n
(iv) nln n, (taking log )log n log n; f4 > f2
f3 = f6
(v) (ln n)n, = (log n )n taking log; n log log n f5 > f3 . f6
(ln n)ln n, taking log ln n. log log n
f3 > f4 > f7

Q31. Arrange following function in the ascending order of growth rate

𝑓1 = (1 + 0.0001)𝑛 , 𝑓2 = ( 𝑛)log 𝑛 ,
𝑓3 = (1.005) 𝑛 , 𝑓4 = (log 𝑛) 𝑛 ,
2
𝑓5 = ( 𝑛)log 𝑛
(a) 𝑓3, 𝑓4, 𝑓2, 𝑓5, 𝑓1 (b)𝑓2, 𝑓5, 𝑓3, 𝑓4, 𝑓1
(c)𝑓1, 𝑓3, 𝑓4, 𝑓2, 𝑓5 (d)𝑓2, 𝑓5, 𝑓1, 𝑓3, 𝑓4

(ADA) Page 14
 Answer: b
Solution:
𝑓1 = (1 + 0.0001)𝑛 , (taking log ) n log 0.0001
1
𝑓2 = ( 𝑛)log 𝑛 , (taking log) (log n)2
2
𝑓3 = (1.005) 𝑛
(taking log ) 𝑛 log 1.005
𝑓4 = (log 𝑛) 𝑛 , (taking log) 𝑛 log log n
2
𝑓5 = ( 𝑛)log 𝑛 (taking log) (log n)2
f2 < f5 < f 3 < f4 < f1

Q32. If 𝑓 𝑛 = 𝑛2 𝑛 + log 𝑛 then which of the following is/are true?

i. 𝑓 𝑛 𝑜(𝑛2.5 ) ii. 𝑓(𝑛)(𝑛 𝑛)
iii. 𝑓 𝑛 Θ(n2.5) iv. 𝑓(𝑛)𝑂(1 + 0.0002𝑛)log 𝑛
(a) i, ii & iii only (b) ii, iii & iv only
(c) iii & iv only (d) All the above

Answer: b
Solution:
𝑓 𝑛 = 𝑛2 𝑛 + log 𝑛
𝑖 𝑓 𝑛 𝑜(𝑛2.5 )  false  (n2.5)
(ii) 𝑓(𝑛)(𝑛 𝑛)  true because n2 𝑛 > n 𝑛
(iii) 𝑓 𝑛 Θ(n2.5)  true
(iv). 𝑓 𝑛 < (1 + 0.0002𝑛)log 𝑛 = f (n) < (1 + 0.0002)  true
Q33. Three programs P1,P2 and P3 have time complexities f1(n), f2(n) and f3(n) respectively,
such that is
f1(n) is O(f2(n)), f2(n) is O(f1(n)), f1(n) is O(f3(n)) and f3(n) is not O(f1(n)).
Which of the following statements must be true?
(a) Program P3 is always faster than P1 and P2 for very large size inputs.
(b) Program P1 is faster than P2 and P3 for very large size inputs.
(c) Program P2 is faster than P1and P3 for very large size inputs.
(d) Program P3 is slower than P1and P2 For very large input

Answer: d
Solution:
Given:
f1 (n) = O(f2(n)),
f2(n) = O(f1(n)),
f1(n) = O(f3(n)) Given
f3(n)  O(f1(n)).
(ADA) Page 15
 means growth rate of f3 is larger than growth rate of f1 & f2
P3 is slower than P1 & P2
Q34. What does it mean to say that an operation takes constant time?
(a) The operation takes the same time on every computer.
(b) The operation takes an amount of time that is independent of the size of its input.
(c) The operation takes an amount of time equal to the size of its input plus some constant.
(d) We cannot conclude any meaning from the given information.

Answer: b
Solution:
O (1) means the operation takes an amount of time that is independent on size of its
input.
Data for next two questions:
Consider the following running time for a program with an input size N:
input size (N) Running time (in seconds)
1000 0.04
5000 1
10000 4
15000 9
20000 16
35000 49
Q35. What will be the complexity of this program?
(a) Θ(n) (b) Θ (n log n)
2
(c) Θ (n ) (d) Θ (2n)

Answer: c
Solution:
(5000)2  1 sec.
1 sec ×(10000 2 )
(10000)2   4 sec.
5000 2
(10000)2  4sec
4 × 20000 2
(20000)2   16 sec
10000 2
i.e.  (n2) is complexity.
Q36. What is the running time of the program (in seconds) if N = 52000? ___________
Answer: 108.16 sec.
Solution:
(20000)2  16 sec.
16 sec × 52000 2
(52000)2   108.16 sec.
20000 2
Data for next two questions:

(ADA) Page 16
Consider the following running time for a program with an input size N:
input size (N) Running time (in seconds)
1000 0.1
2000 0.8
3000 2.7
4000 6.4
5000 12.5
6000 21.6
Q37. What will be the estimated running time of the program (in seconds) on input size N =
15000? ______

Answer: 337.5
Solution:
(1000)3  0.1
0.1 ×8
(2000)3  = 0.8
0.8 × 150 3
(15000)3  = 337.5
20 3
Q38. What will be the complexity of given program?
(a) Θ(n) (b) Θ (n log n)
(c) Θ (n2) (d) Θ (n3)

Answer: d
Solution:
Complexity of the code is Θ (n3) by doing option elimination.

Q39. Assume that a merge sort algorithm in the worst case takes 256 seconds for input size 256.
Which of the following most closely approximates the maximum input of size of a
problem that can be solved in 1280 seconds?
(a)512 (b) 768
(c) 1024 (d) 1280

Answer: c
Solution:
Input 256 take 256 sec
256 log 256  256 sec.
n log n  1280
256×𝑛 log 𝑛
= 1280
256 log 256
𝑛 log 𝑛
= 1280
8
n log n = 1280  8
(ADA) Page 17
 n log n = 10240
1024 log 1024 = 10240
Q40. Consider an algorithm that takes 29 seconds for input size N = 3364 in worst case. If it is
given that worst case complexity of this algorithm is Θ( 𝑛), then which of the following
most closely approximates the maximum input size of a problem that can be solved in
45seconds?
(a) 2025 (b) 32400
(c) 8100 (d) 24300

Answer: c
Solution:
N = 3364 take 29 sec
= 3364  29sec.
N = X take 45 sec
= 𝑥  45 sec
29 × 𝑥
= = 45 sec.
3364
45  58
𝑥 = 90
x = (90)2
x = 8100

Q41. Suppose you have following algorithms to solve a problem:

 Algorithm A solves an instance of size n by recursively solving seven instances of size
n/2, then combining their solutions in time O(n3).
 Algorithm B solves an instance of size n by recursively solving twenty five instances of
size n/4 and then combining their solution in time O(n 2).
 Algorithm C solves an instance of size n by recursively solving five instances of size 3n,
and then combining their solutions in time O (n).
Which one is preferable?
(a) Algorithm A (b) Algorithm B
(c) Algorithm C (d) insufficient information

Answer: b
Solution:
T (n) = 7 T (n/2) + n3
= 𝑛log 2 7 = n2.30
n3 > n2.8
 Algo A complexity is O (n3)

(ADA) Page 18
 Algo B:
T (n) = 25 T (n /4) + n2
Complexity O (n2.32)
Complexity of Algo: B is smaller than all algo.
Algo C:
T (n) = 5T (3n) + O (n) never ends.
Q42. Consider a sorting algorithm with worst-case complexity of Θ (log2 n). If it takes 1 ms for
execution for n = 1024, then how long it will take (in ms) for n = 65536? _________

Answer: 1.6
Solution:
n = 1024  1 n sec
n = 65536?
Complexity O (log2n)
log21024  1 sec
1 ×log 65536
log 65536  = 1.6
log 1024

Q43. Consider a sorting algorithm with worst-case complexity of Θ (n log2 n). If it takes 1 ms for
execution for n = 1024, then how long it will take (in ms) for n = 65536? _________

Answer: 102.4
Solution:
Complexity = O (n log n)
n = 1024  1 ms
n = 65536?
1024 log 1024 – 1 msec
1 ×65536 log 65536
65536 log 65536 
1024 log 1024
Q44. Suppose you run a O(log n) algorithm with an input size of 1024 and the algorithm
requires 110 operations. When you double the input size to 2048, the algorithm now
requires 121 operations. What is your best guess for the number of operations required
when you again double the input size to 4096?
(a) 130 (b) 131
(c) 132 (d) 133
Answer: c
Solution:
log 1024  110 operation
log 2048  121 operation

(ADA) Page 19
 log 4096  ?
121 ×log 4096
= = 132
log 2048
For the next two questions: Given the following data (in seconds) for some sorting algorithm
with N distinct value in random order:
Input Size(N) 1000 2000 4000 8000 16000
Time in second(in ms) 0.6 1.3204 2.8816 6.2449 13.4532
Q45. What will be the complexity for given algorithm?
(a) Θ(n) (b) Θ (n log n)
(c) Θ (n2) (d) Θ (n 𝑛)

Answer: b
Solution:
Through option elimination complexity is Θ (n log n)
1000. log 1000  0.6
0.6 ×2000 log 2000
2000 log 2000  = 1.3204
1000 log 1000

Q46. What will be the estimated running time of given algorithm (in seconds) on input of size N
= 64000?(Round off upto 2 decimal digits)? __________________

Answer:61.52
Solution:
8000 log 8000  6.2449
64000 log 64000?
6.2449 ×64000 log 64000
= = 61.52
8000 log 8000

Q47. Consider two Algorithms A and B has Θ (n log2n) and Θ (n2) respectively to solve a
problem. For n = 2048, if the algorithm A takes 10 microseconds and B takes only 1
microseconds, then which of the two is the best algorithm for n = 220?
(a) A (b) B
(c) Both A& B (d) insufficient information

Answer: A
Solution:
Algo A = O(nlogn)
Algo B = O (n2)
2048 log 2048  10  sec

(ADA) Page 20
 220 log 220 ?
10 × 220 log 220
= = 10  29  1.818 = 9308.16  sec.
211 𝑙𝑜𝑔 211
(2048)2  1  sec.
240
(220)2 
222
Algo A is best.
Q48. Consider the following observed execution time while running a sorting algorithm:
1. Algorithm takes 10 sec if there are 216 elements in array and elements are in random
order.
2. Algorithm takes 2560 sec if there are 220 elements in array and elements are in random
order.
3. Algorithm takes 4 sec if there are 212 elements in array and elements are in ascending
order.
4. Algorithm takes 64 sec if there are 216 elements in array and elements are in ascending
order. Based on the timing data, what sorting algorithm it is?
(a) Selection sort (b) Quick sort
(c) Merge sort (d) insertion sort
Answer: d
Solution:
Input size Time in sec.
16
Random 2 10
20
order 2
Ascending 212 4
16
order 2 64
2
Eliminate are in random order then O(n )
(216)2  10 sec
10 ×210
(220)2   10  28 = 2560 sec
232
(212)  4 sec
4 ×216
216  = 24  4 = 64 sec
212
Elements are in descending order then O (n).
Q49. Which of the following statements is/are false?
(1) The worst case time complexity of an algorithm is (n). The algorithm will execute in
time T(n)  (n2) for some input data.
(2) The worst case time complexity of an algorithm is (n). The algorithm will execute in
time T (n)  (n2) for every input data.
(3) For the best case data the algorithm takes time θ(n). The algorithm may execute in
time T(n)  (n2) for some input data.
(4) For the best case data the algorithm takes time θ(n). The algorithm will execute in time
T(n)  (n2) for every input data.

(ADA) Page 21
 (a) 1 & 2 only (b) 3 & 4 only
(c) 3 only (d) 1, 2 & 4 only
Q50. A quadratic algorithm with processing time T(N) = cN2 spends T(N) seconds for
processing N data items. How much time will be spent for processing N = 4000 data
items, assuming that N = 100 and T(N) = 1ms?______________
Answer: 1600
Solution:
(100)2  1 msec
1 𝑚𝑠𝑒𝑐 ×4000 ×4000
(1000)2 
100 ×100
= 40  40 = 1600
Q51. An algorithm with time complexity O(f(n)) and processing time T(n) = cf(n), where f(n) is
a known function of n, spends 10 ms to process 2000 data items. How much time will be
spent to process 100,000 data items if f(n) = n3? (in seconds)_____________

Answer: 1250
Solution:
(2000)3 – 10 msec
10 ×10 15 10 ×10 15
(100,000)3  = = = 1250 sec.
2000 3 23 ×10 9
Q52. In this problem you will compute the asymptotic time complexity of the following divide-
and-conquer algorithm. You may assume that n is a power of 2. (NOTE: It doesn't matter
what this does!)
float useless(A){
n = A.length;
if (n==1){
return A[0];
}
//let A1,A2 be arrays of size n/2
for (i=0; i <= (n/2)-1; i++){
A1[i] = A[i];
A2[i] = A[n/2 + i];
}
for (i=0; i<=(n/2)-1; i++){
for (j=i+1; j<=(n/2)-1; j++){
if (A1[i] == A2[j])
A2[j] = 0;
}
}
b1 = useless(A1);
b2 = useless(A2);
return max(b1,b2);
}
(ADA) Page 22
 (a) 𝜃 𝑛 (b) 𝜃 𝑛2
(c)𝜃 𝑛 log 𝑛 (d) 𝜃 𝑛
Answer: 8
Solution:
𝑛 𝑛 𝑛2
For loop run for  =  O (n2)
2 2 4
Q53. For the following program fragment, what will be the worst-case asymptotic time
complexity (as a function of n)?
for (i=0; i<=n-1; i++){
for (j=i+1; j<=n-1; j++){
print(“Be always happy”)
}
}

(a)𝜃(𝑛)
(b)𝜃(𝑛2 )
(c)𝜃(𝑛 log 𝑛)
(d)𝜃( 𝑛)

Answer: b
Solution:
i runs for (n) times
j runs for n times
n  n = n2
Instruction for next three questions: Analyze the running time of each of the following three C
functions. Each of the functions takes as input an integer array arrand its length ‘n’. For each
function you should give the running time T(n) as a function of „n’ and then give the appropriate
Big-O classification. You can assume for simplicity that n is divisible by 2.
Q54. What will be the worst case time complexity for the following code?
int fun1(int arr[], int n)
{
int result = 25;
int i = n;
while (i > 1)
{
for (int j = 0; j < n; j++)
{
result += 1;
result += 3 * arr[j];
}

(ADA) Page 23
 i = i / 2;
}
return result;
}
(a) 𝜃(𝑛)
(b) 𝜃(𝑛2 )
(c)𝜃(𝑛 log 𝑛)
(d) 𝜃( 𝑛)

Answer : c
Solution:
i runs for logn time where as j runs n times for every i
 complexity is  (n log n)
i=n j runs for n times
𝑛
i= j runs for n times
2
𝑛
i= j runs for n times
22
.
.
.
𝑛 𝑗 𝑟𝑢𝑛𝑠 𝑓𝑜𝑟 𝑛 𝑡𝑖𝑚𝑒𝑠
i=
2𝑘 𝑛 ×log 𝑛 𝑡𝑖𝑚𝑒𝑠
𝑛
= 1, n = 2k = k = log n
2𝑘
 Loop i runs for log 2 𝑛 times whereas j runs for n times for every i loop.

Q55. What will be the worst case time complexity for the following code?
int fun2(int arr[], int n)
{
int result = 0;
for(int i = 0; i < n/2; i++)
{
result += 3*arr[i];
}
for(i = n/2; i < n; i++)
{
result += 3 * arr[i];
result += 5 * arr[i];
}
return result;

(ADA) Page 24
 }
(a) 𝜃(𝑛) (b) 𝜃(𝑛2 )
(c)𝜃(𝑛 log 𝑛) (d) 𝜃( 𝑛)

Answer: A
Solution:
𝑛
1st for loop runs for times
2
𝑛
2nd for loop runs for − 1 times
2
 (n) times
Q56. What will be the worst case time complexity for the following code?
int fun3(int arr [], int n)
{
int result = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < 7; j++){
for (int k = 0; k < n; k++)
result + = j * j + arr[k];
}
}
}
return result;
}
(a) 𝜃(𝑛) (b) 𝜃(𝑛2 )
(c) 𝜃(𝑛 log 𝑛) (d) 𝜃( 𝑛)

Answer: b
Solution:
i runs for n times
j runs for 7 times
k runs for n times
7  n  n = 7n2
 Complexity = (7n2) =  (n2)
Q57. Which one of the following sorting algorithms always has the running time recurrence
equation
T(n) = T(n − 1) + n?
(a) Insertion sort (b) Bubble sort
(c) Heap sort (d) Both a & b

(ADA) Page 25
 Answer: b
Solution:
T(n) = T(n − 1) + n
For 1st Iteration it seems for n times
for 2nd Iteration it runs for n - 1 times
for 3rd Iteration it runs for n – 2 times
.
.
.
Bubble sort
It can‟t be Insertion sort because in 1st Iteration it take 1 comp then 2 comp and so on.
Q58. Find the complexity of the following code, where n is given as input:
i = n;
while(i > 1)
{
j = i;
while (j < n)
{
k = 0;
while (k < n)
{
k = k + 2;
}
j = j * 2;
}
i = i / 2;
}
(a)𝜃((log 𝑛) )3
(b)𝜃(𝑛 log 𝑛)
(c)𝜃(𝑛 log 𝑛)
2
(d)𝜃(𝑛 (log 𝑛)2 )

Answer: d
Solution:
i = n, j = n, k = runs for n/2
j = n/2, k runs for n/2
j = n/4, k runs for n/2
j = n/2k = k runs for n/2
 j runs for log n whereas k runs for n times for every j and i runs for log n times.
 over all complexity (logn) (logn) (n/2)
  
(ADA) Page 26
 i j k

Q59. 3𝑇 𝑛 − 1 ; 𝑖𝑓𝑛 > 0

What will be the complexity of the below recurrence relation: T(n) =
1; 𝑜𝑡𝑕𝑒𝑟𝑤𝑖𝑠𝑒
(a) Θ (3n) (b)Θ(n2)
(c) Θ(n3) (d) Θ (1)

Answer: A
Solution:
3𝑇 𝑛 − 1 , 𝑖𝑓 𝑛 > 0
(n) =
1, 𝑜𝑡𝑕𝑒𝑟𝑤𝑖𝑠𝑒
T(n) = aT(n-b) +nk if a>1 then
Complexity is O(an/b nk)
Therefore the complexity of above recurrence is O(3n)
Q60. Find the complexity of the below recurrence :
2𝑇 𝑛 − 1 − 1; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑂𝑡𝑕𝑒𝑟𝑤𝑖𝑠𝑒
n
(a) Θ (3 ) (b) Θ(n2)
(c) Θ(n3) (d) Θ (1)
Answer: d
Solution:
2𝑇 𝑛 − 1 − 1 𝑖𝑓 𝑛 > 0
T (n)=
1 𝑜𝑡𝑕𝑒𝑟𝑤𝑖𝑠𝑒
T (n) = 2T (n – 1) – 1
T (n – 1) = 2T (n – 2) – 1
T (n ) = 2 T (n – 2 ) – 2 – 1
T(n) = 2T (n – 3) – 22 – 2 - 20
= 2T (n – (n – 1) – [2n – 2 +2n – 3 + - - - 20]
= 2 – [2n-1 + 2n-2 + - - - -+ 20]
=  Complexity is O (1)
Because it is 2 – [2n – 1]
= -2n + 1

Instruction for next questions: Find the complexity of below recurrence:

Q61. 𝑇 𝑛 − 1 + 1; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ(n2)
(c) Θ(n3) (d) Θ (1)

(ADA) Page 27
 Answer: A
Solution:
T (n) = 𝑇 𝑛 − 1 + 1 𝑛 > 0
1 𝑛=1
T (n) = T (n – 1) + 1
T (n – 1) = T (n – 2) + 1
T (n) = T (n – 2) + 2
T (n) = T (n – k) + k
If k = n -1
 T (n) = T (1) + n – 1  T (1) = 1
 Complexity O (n – 1)

Q62. 1
𝑇 𝑛 − 1 + ; 𝑖𝑓𝑛 > 0
𝑇 𝑛 = 𝑛
1; 𝑖𝑓𝑛 = 1
(a) Θ (1) (b) Θ(log n)
(c) Θ(n log n) (d) Θ (n)

Answer: B
Solution:
1
𝑇 𝑛−1 + 𝑖𝑓 𝑛 > 0
T (n) = 𝑛
1, 𝑖𝑓 𝑛 = 1
1
T (n) = T (n – 1) +
𝑛
1
T (n – 1) = T (n2) +
𝑛−1
.
.
1 1
T (n) = T (n – 2) + +
𝑛−1 𝑛
1 1 1 1
T (n) = T (1) + + + + . . .
2 3 4 𝑛
1 1 1 1
T (n) = + + + …
1 2 3 𝑛
T (n) =  (log n)
Q63. 𝑇 𝑛 − 1 + log 𝑛 ; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
(a) Θ (1) (b) Θ (log n)
(c) Θ(n log n) (d) Θ (n)

(ADA) Page 28
 Answer: c
Solution:
T (n) = T (n – 1) + logn
T (n – 1) = T (n – 2) + log (n -1)
T (n – 2) = T (n – 3) + log (n – 2)
T (n ) = T ( n- k) + log (n - (k – 1) + . . . + log n
= T (1) + log 2 + log 3 + . . . log n
= log (1, 2 , 3 , 4 . . . . n)
= log n!
= n log n

Q64. 𝑇 𝑛 − 1 + 𝑛; 𝑖𝑓𝑛 > 0

𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
(a) Θ ( 𝑛) (b) Θ (n)
(c) Θ(n 𝑛) (d) Θ (n log n)

Answer: c
Solution:
𝑇 𝑛 − 1 + 𝑛; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1

T (n) = 𝑛 + 𝑛 − 1 + 𝑛 − 2 + 𝑛 − 3 + . . . + n =  ( n 𝑛)
1
 𝑛𝑃=1 𝑘 𝑃  𝑛𝑝 + 1
𝑃+1
Q65. 𝑇 𝑛 − 1 + 𝑛; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ (n log n)
(c) Θ (n 𝑛) ) (d) Θ (n2)

Answer: d
Solution:
𝑇 𝑛 − 1 + 𝑛; 𝑖𝑓𝑛 > 0
T 𝑛 =
1; 𝑖𝑓𝑛 = 1

T (n) = T (n – 1) + n
T (n -1) = T ( n – 2) + n – 1
T (n) = T( n -2) + n + n – 1
= n + n – 1 + n -2 +…+1
𝑛 (𝑛+1)
= =  (n2)
2
Q66. 𝑇 𝑛 − 1 + 𝑛𝑙𝑜𝑔𝑛; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ (n log n)
(c) Θ (n (log n)2) (d) Θ (n2log n)

(ADA) Page 29
 Answer: d
Solution:
𝑇 𝑛 − 1 + 𝑛𝑙𝑜𝑔𝑛; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
T (n – 1) = T ( n – 2) + ( n – 1) log ( n – 1)
T ( n – 2) = T ( n – 3) + ( n – 2) log ( n – 2)
T (n) = T ( n – 3) + ( n – 2) log (n – 2) + (n – 1) log ( n – 2) + log (n)
equivalence will be
= 2log2 + 3 log 3 + 4 log 4 + . . . + nlog n
= nlog n + (n – 1) log ( n – 1) + . . . .+ (n – 1 n .2)) log2
= n log n + n log n – 1 = . . . (n log2) – [log (n – 1 ) + log (n – 2) . . .
= n [log n!] – log n!
= (n- 1) logn!
Q67. 𝑇 𝑛 − 1 + 𝑛2 ; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
(a)Θ (n2) (b)Θ (n2log n)
(c) Θ (n3) (d)Θ (n4)

Answer: c
Solution:
𝑇 𝑛 − 1 + 𝑛2 ; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
T (n) = T (n – 1) + n 2

T (n – 1) = T ( n-2) + (n -1)2
.
.
T (n) = 12 + 22 + 32 + . . . .n2
= [n (n + 1) (2n + 1)]/6
=  (n3)
Q68. 𝑇 𝑛 − 1 + 𝑛𝑘 ; 𝑖𝑓𝑛 > 0
𝑇 𝑛 = ; Where k is any non-negative integer.
1; 𝑖𝑓𝑛 = 1
(a) Θ (1) (b)Θ (nk)
2
(c)Θ (nk+1) (d)Θ (𝑛𝑘 )

Answer: c
Solution:
𝑇 𝑛 − 1 + 𝑛𝑘 ; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
T (n) = nk + (n – 1)k + ( n- 2)k + . . . 1k
𝑛 𝑘+1
= 𝑛
=
𝑝=1 𝑘𝑛 =  (nk + 1)
𝑘+1
Q69. 𝑇 𝑛 − 1 + 2𝑛 ; 𝑖𝑓𝑛 ≥ 1
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 0

(ADA) Page 30
 (a) Θ (2n) (b) Θ(2n+1)
(c) both a & b (d) Θ (n.2n)

Answer: c
Solution:
𝑇 𝑛 − 1 + 2𝑛 ; 𝑖𝑓𝑛 ≥ 1
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 0
T (n) = T (n – 1) + 2 n

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

.
.
20+ 21 + 22 + 23 + 24 + . . . + 2n = 2n + 1-1 =  (2n)
Q70. 2𝑇 𝑛 − 1 + 1; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
n
(a)Θ(2 ) (b)Θ(n2)
(c)Θ(n log n) (d)Θ(n)

Answer: A
Solution:
2𝑇 𝑛 − 1 + 1; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
T (n) = 2 T( n – 1) + 1
T ( n – 1) = 2T ( n – 1) + 1
T (n) = 2T (n – 2) + 2 + 1
= 2n + 2n – 1 + . . . + 1
=  (2n)
Q71. 1
2𝑇 𝑛 − 1 + ; 𝑖𝑓𝑛 > 0
𝑇 𝑛 = 𝑛
1; 𝑖𝑓𝑛 = 1
2 𝑛 −𝑟 1
(a) 𝑛𝑟=1 (b) 𝑛
𝑟=1 𝑟.2𝑟
𝑟
𝑛 1
(c)2𝑛 𝑟=1 𝑟.2𝑟 (d) Both a & c

Answer: D
Solution:
1
2𝑇 𝑛 − 1 + ; 𝑖𝑓𝑛 > 0
𝑇 𝑛 = 𝑛
1; 𝑖𝑓𝑛 = 1
T (n) = 2T (n – 1) + 1/n - - - - -(1)
1
T (n – 1) = 2T (n – 2) + - - - - (2)
𝑛−1
Putting eq (2) in eq (1)

(ADA) Page 31
 2 1
T (n) = 2T (n – 2) + + - - - -(3)
𝑛−1 𝑛
1
T ( n – 2) = 2T (n – 3) + - - - -(4)
𝑛−2
2 1
T (n) = 22T[20T (n – 3) +1/n2]+ +
𝑛−1 𝑛
22 2 1
T (n) = 23T (n – 3) + + +
𝑛−2 𝑛−1 𝑛
2𝑘−1 1
T (n ) = 2k T (n – k) + +...+
𝑛−(𝑘−1) 𝑛
k = n – 1 then T (1) = 1
2𝑛 −2 2𝑛 −3 2𝑛 −𝑛
T (n) = 2n-1 + + + ⋯+
2 3 𝑛
2𝑛 2𝑛 2𝑛 2𝑛
T (n) = + + + …+
2 22 .2 23 .3 2𝑛 .𝑛
1 1 1 1 1
= 2n [ + + + + ….+ ]
2 22 .2 23 .3 24 .4 2𝑛 .𝑛
𝑛 1 2𝑛 2𝑛 −𝑟
= 2n or 𝑛𝑟=1 𝑟 =
𝑟=1 𝑟 .2𝑟
𝑛
𝑟=1
𝑛.2 𝑟
Q72. 2𝑇 𝑛 − 1 + log 𝑛 ; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
log 𝑟 log 𝑟
(a) 𝑛
𝑟=2 2𝑟 (b) 𝑛
𝑟=2 2𝑟 + 2n-1
𝑛 log 𝑟 1
(c)2𝑛 𝑟=2 2𝑟 + (d)Both b & c
2
Answer: d
Solution:

2𝑇 𝑛 − 1 + log 𝑛 ; 𝑖𝑓𝑛 > 0

𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
T (n) = 2T (n – 1) + log n - - - - - - -(1)
T (n – 1) = 2T (n – 2) + log (n – 1) - - -(2)
putting value in eq (2) in eq (1)
T (n) = 22 T (n – 2) + 2 log (n – 1) + log n
T (n) = 23log (n – 3) + 22log (n – 2) + 2 log (n – 1) + log n
T (n) = 2n-1 + 2n-2 log2 + 2n-3 log 3 + - - - + logn
2n 2𝑛 𝑙𝑜𝑔 2 2𝑛 𝑙𝑜𝑔 3 2𝑛
+ + + - - - -+ 𝑙𝑜𝑔𝑛
2 22 23 2𝑛
𝑙𝑜𝑔 2 𝑙𝑜𝑔 3 𝑙𝑜𝑔𝑛 2𝑛
2n [ 2 + 3 + - - - -+ ]+
2 2 2𝑛 2
n 𝑛 𝑙𝑜𝑔𝑟 1
2 [ 𝑟=2 𝑟 + ]
2 2

Q73. 2𝑇 𝑛 − 1 + 𝑛; 𝑖𝑓𝑛 > 0

𝑇 𝑛 = ; (select tightest upper bound)
1; 𝑖𝑓𝑛 = 1
(a) O ( 𝑛2n) (b) O (n2)
(c) Θ(n log n) (d) Θ (n)

(ADA) Page 32
 Answer: A
Solution:
2𝑇 𝑛 − 1 + 𝑛; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
O ( 𝑛. 2n) mater theorem.
Q74. 2𝑇 𝑛 − 1 + 𝑛; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
n
(a) O ( 𝑛2 ) (b)Θ (n2)
(c) O (n.2n) (d) Θ (n)

Answer: c
Solution:
2𝑇 𝑛 − 1 + 𝑛; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
By master theorem
O (2n.n)
Q75. 2𝑇 𝑛 − 1 + 𝑛𝑙𝑜𝑔𝑛; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
𝑛
(a)2 𝑛−1 𝑛−𝑟
+ 𝑟=2 2 𝑟𝑙𝑜𝑔𝑟 (b) 𝑛𝑟=2 2𝑛−𝑟 𝑟𝑙𝑜𝑔𝑟
(c)2 𝑛−1
+ 𝑛−2 𝑟
𝑟=0 2 (𝑛 − 𝑟)𝑙𝑜𝑔 (𝑛 − 𝑟) (d) Both a & c

Answer: d
Solution:
2𝑇 𝑛 − 1 + 𝑛𝑙𝑜𝑔𝑛; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
T (n) = 2T(n-1) + n logn - - -- -(1)
T (n -1) = 2T (n – 2) + (n – 1) log (n – 1) - - - - (2)
T (n) = 2 [2T (n – 2) + (n – 1) log (n – 1) ] + n log n
T (n) = 22 T (n – 2) + 2 (n – 1) log(n -1) +n log n
T (n) = 2n -1 + 2n-2. 2log2 + 2n-3. 3log3 + - - - -+2 (n – 1) log n- 1 + n log n - -- -(3)
2n-1 + 𝑛𝑟=2 2𝑛−𝑛 𝑟𝑙𝑜𝑔𝑟
eq (3) is written as
n logn + 2 (n – 1) log (n – 1) + 22 (n – 2) log (n – 2) + 23(n – 3) log2
2n -1 + 𝑛−2 𝑟
𝑟=0 2 𝑛 − 𝑟 log(𝑛 − 𝑟)

Q76. 2𝑇 𝑛 − 1 + 𝑛2 ; 𝑖𝑓𝑛 > 0

𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
(a) O ( 𝑛2n) (b) Θ (n2)
(c) O (n.2n) (d) O (n2.2n)
(ADA) Page 33
 Answer: d
Solution:
2𝑇 𝑛 − 1 + 𝑛2 ; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
O (n2. 2n)
Q77. 2𝑇 𝑛 − 1 + 𝑛3 ; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
n
(a) O ( 𝑛2 ) (b) Θ (n2)
(c) O (n.2n) (d) O (n3.2n)
Answer: d
Solution:
2𝑇 𝑛 − 1 + 𝑛3 ; 𝑖𝑓𝑛 > 0
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
3 n
O (n .2 ) master theorem.

Q78. 𝑛
4𝑇 + 1; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
(a) Θ ( 𝑛) (b) Θ (n2)
(c) Θ (n) (d) Θ (n log n)

Answer: b
Solution:
𝑛
4𝑇 + 1; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
=𝑛 log 2 4
> 1 = n2 > 1
 Θ (n ) 2

Q79. 𝑛
4𝑇 + log 𝑛 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
(a) Θ ( 𝑛) (b) Θ (n2)
(c) Θ (n) (d) Θ (n log n)

Answer: b
Solution:
𝑛
4𝑇 + log 𝑛 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
2 2
Θ (n ) because n > 1

(ADA) Page 34
Q80. 𝑛
4𝑇 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
(a) Θ ( 𝑛) (b) Θ (n2)
(c) Θ (n) (d) Θ (n log n)

Answer: b
Solution:
𝑛
4𝑇 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
= 𝑛log 2 4 = n2 > 𝑛
 complexity is Θ (n2)
Q81. 𝑛
4𝑇 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
(a) Θ ( 𝑛) (b) Θ (n2)
(c) Θ (n) (d) Θ (n log n)
Answer: b
Solution:
𝑛
4𝑇 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
2
complexity Θ (n ) by master theorem.
Q82. 𝑛 𝑛
4𝑇 + ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2 log 𝑛
1; 𝑖𝑓𝑛 = 1
(a) Θ ( 𝑛) (b) Θ (n2)
(c) Θ (n) (d) Θ (n log n)
Answer: b
Solution:
𝑛 𝑛
4𝑇 + ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2 log 𝑛
1; 𝑖𝑓𝑛 = 1
= 𝑛log 2 4 > n
= Θ (n2)
Q83. 𝑛 𝑛
2𝑇 + ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2 log 𝑛
1; 𝑖𝑓𝑛 = 1
(a) Θ ( 𝑛) (b) Θ (n2)
(c) Θ (n log log n) (d) Θ (n log n)

(ADA) Page 35
 Answer: c
Solution:
𝑛 𝑛
2𝑇 + ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2 log 𝑛
1; 𝑖𝑓𝑛 = 1
=𝑛 log 10 𝑎
=𝑛 log 2 2
=n
Θ (n loglog n)  p = -1 then T (n) = Θ (𝑛log 𝑏 𝑎 log log n)

Q84. 𝑛
4𝑇 + 𝑛 log 𝑛 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
(a) Θ ( 𝑛) (b) Θ (n2)
(c) Θ (n) (d) Θ (n log n)

Answer: b
Solution:
𝑛
4𝑇 + 𝑛 log 𝑛 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
2
Θ (n ) by master theorem.
Q85. 𝑛
4𝑇 + 𝑛 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
(a) Θ ( 𝑛) (b) Θ (n2)
(c) Θ (n) (d) Θ (n log n)

Answer: b
Solution:
𝑛
4𝑇 + 𝑛 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
2
Θ (n ) by master theorem.
Q86. 𝑛
4𝑇 + 𝑛2 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
(a) Θ (𝑛 𝑛) (b) Θ (n2)
(c) Θ (n2log n) (d) Θ (n log n)

Answer: c
Solution:

(ADA) Page 36
 𝑛
4𝑇 + 𝑛2 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
=𝑛 log 2 4
=n 2

f (n) = n2
f (n) = n2
 𝑛log 𝑏 𝑎 = f (n) then f (n) = 𝑛log 𝑏 𝑎 log n
Θ (n2log n)
Q87. 𝑛
4𝑇 + 𝑛2 log 𝑛 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
(a) Θ (𝑛𝑙𝑜𝑔𝑛) (b) Θ (n2)
(c) Θ (n2log n) (d) Θ ((n log n)2)

Answer: d
Solution:
𝑛
4𝑇 + 𝑛2 log 𝑛 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2
1; 𝑖𝑓𝑛 = 1
=𝑛 log 𝑏 𝑎
= f (n)
n2 log2 n = (n log n)2
Q88. 𝑛
2𝑇 + log log 𝑛 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4
1; 𝑖𝑓𝑛 = 1
(a) Θ ( 𝑛) (b) Θ (n)
(c) Θ (log log n) (d) Θ ((log log n)2)
Answer: a
Solution:
𝑛
2𝑇 + log log 𝑛 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4
1; 𝑖𝑓𝑛 = 1
1
= 𝑛log 𝑏 𝑎 = 𝑛log 4 2 = 𝑛2 > f (n)
1
= Θ (𝑛2 ) = Θ ( 𝑛)
Q89. 𝑛
2𝑇 + 𝑙𝑜𝑔𝑛 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4
1; 𝑖𝑓 𝑛 = 1
𝑛log 𝑏 𝑎 = 𝑛log 4 2 = Θ ( 𝑛 )> f (n)
Answer : A
Q90. 𝑛
2𝑇 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4
1; 𝑖𝑓𝑛 = 1
(a) Θ ( 𝑛) (b) Θ (n)

(ADA) Page 37
 (c) Θ (log log n) (d) Θ ( 𝑛 log n)

Answer: d
Solution:
𝑛
2𝑇 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4
1; 𝑖𝑓𝑛 = 1
= 𝑛log 4 2 = Θ ( 𝑛) = f (n)
 Θ ( 𝑛 log n) is the complexity.

Q91. 𝑛
2𝑇 + 𝑛0.57 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ (n0.57)
(c) Θ (n log n) (d) Θ (n0.57 log n)

Answer: b
Solution:
𝑛
2𝑇 + 𝑛0.57 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4
1; 𝑖𝑓𝑛 = 1
= 𝑛log 2 4 = n0.5 < n0.57
 Θ (n0.57) master theorem.
Q92. 2𝑇
𝑛
+
𝑛 𝑛
; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4 (log 𝑛)2 ;
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b)O(𝑛 𝑛)
𝑛 𝑛 𝑛 𝑛
(c)Θ( ) (d)O( )
(log 𝑛)2 (log 𝑛)2

Answer: b
Solution:
𝑛 𝑛 𝑛
2𝑇 + ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4 (log 𝑛)2
1; 𝑖𝑓𝑛 = 1
= 𝑛log 𝑏 𝑎 = 𝑛log 4 2 = 𝑛
f (n) > 𝑛log 𝑏 𝑎
O(𝑛 𝑛)
Q93. 𝑛
2𝑇 + 𝑛(log 𝑛)2 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ ( 𝑛)
(ADA) Page 38
 (c) Θ (n (log n)2) (d) Θ (n(log n)3)
Answer: c
Solution:
𝑛
2𝑇 + 𝑛(log 𝑛)2 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4
1; 𝑖𝑓𝑛 = 1
=𝒏 𝐥𝐨𝐠 𝒃 𝒂
< f (n)
 Θ (n (log n)2)
Q94. 𝑛
2𝑇 + 𝑛(log 𝑛)2 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ ( 𝑛)
(c) Θ ( 𝑛(log 𝑛)2 ) (d) Θ ( 𝑛(log 𝑛)3 )

Answer: d
Solution:
𝑛
2𝑇 + 𝑛(log 𝑛)2 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4
1; 𝑖𝑓𝑛 = 1
=𝑛 log 𝑏 𝑎
= f (n)
𝑛= 𝑛
complexity is 𝑛(log 𝑛)3
Q95. 𝑛 𝑛
2𝑇 + ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4 (log 𝑛)2
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ ( 𝑛 )
(c) Θ ( 𝑛(log 𝑛)2 ) (d) Θ ( 𝑛(log 𝑛)3 )

Answer: b
Solution:
𝑛 𝑛
2𝑇 + ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4 (log 𝑛)2
1; 𝑖𝑓𝑛 = 1
=𝑛 log 𝑏 𝑎
= f (n)
𝑛= 𝑛
 complexity is Θ ( 𝑛 )
Q96. 𝑛 𝑛
2𝑇 + ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2 (log 𝑛)2
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ ( 𝑛)
(c) Θ ( 𝑛(log 𝑛)2 ) (d) Θ ( 𝑛(log 𝑛)3 )

(ADA) Page 39
 Answer: a
Solution:
𝑛 𝑛
2𝑇 + ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2 (log 𝑛)2
1; 𝑖𝑓𝑛 = 1
Θ (n) because 𝑛 log 𝑏 𝑎
= f (n) & p > -1
Q97. 𝑛 𝑛
2𝑇 + ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2 log 𝑛
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ ( 𝑛)
(c) Θ ( 𝑛(log 𝑛)2 ) (d) Θ ( 𝑛(log 𝑛)3 )

Answer: a
Solution:
𝑛 𝑛
2𝑇 + ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2 log 𝑛
1; 𝑖𝑓𝑛 = 1
=𝑛 log 𝑏 𝑎
> f (n)
= Θ (n)
Q98. 𝑛 𝑛𝑙𝑜𝑔 2 5
5𝑇 + ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2 log 𝑛
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ ( 𝑛)
(c) Θ (𝑛𝑙𝑜𝑔 2 5 log log 𝑛) (d) Θ (𝑛𝑙𝑜𝑔 2 5 )

Answer: c
Solution:

𝑛 𝑛𝑙𝑜𝑔 2 5
5𝑇 + ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2 log 𝑛
1; 𝑖𝑓𝑛 = 1
= 𝑛log 2 5 = f (n)
= Θ (𝑛𝑙𝑜𝑔 2 5 log log 𝑛)

Q99. 𝑇 𝑛 + 1; 𝑖𝑓𝑛 > 1

𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ ( 𝑛)
(c) Θ (log log 𝑛) (d) Θ (n log log n)

(ADA) Page 40
 Answer: c
Solution:
𝑇 𝑛 + 1; 𝑖𝑓𝑛 > 1
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
T (n) = T 𝑛 + 1
n = 2k  k = log n
𝑘
T (2k) = T (22 ) + 1
5 (k) = 5 (k/2) + 1
= 𝑘 log 𝑏 𝑎 = 𝑘 log 2 1 = k0 = 1 f (n)
 Θ (log k) = Θ (log log 𝑛)
Q100. 𝑇 𝑛 + log 𝑛 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ ( 𝑛)
(c) Θ (log log 𝑛) (d) Θ (log n)

Answer: d
Solution:
𝑇 𝑛 + log 𝑛 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
T (n) = T 𝑛 + log 𝑛
n = 2k  k = log n
T (2k) = T (2k/2) + log 2k
s (k) = s (k/2) + k
Θ (k)
 Θ (log n)
Q101. 𝑇 𝑛 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ ( 𝑛)
(c) Θ (log log 𝑛) (d) Θ (log n)

Answer: a
Solution:
𝑇 𝑛 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
n=2 k

s (k) = s (k/2) + 2k
= 𝑛log 2 1 < 2k
 complexity Θ (2k) = Θ (n)

(ADA) Page 41
Q102. 𝑘
𝑇 𝑛 + 1; 𝑖𝑓𝑛 > 1
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 𝑎
(a) Θ (logklogan) (b) Θ ( 𝑛)
(c) Θ (log 𝑛) (d) Θ (logalogkn)

Answer: a
Solution:
𝑘
𝑇 𝑛 + 1; 𝑖𝑓𝑛 > 1
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 𝑎
1/k
T (n) = T (n ) + 1 - - - - - -(1)
1
T (n1/k) = T ( 𝑛 𝑘2 ) + 1 - - - -(2)
1
T (n) = T ( 𝑛 𝑘2 ) +2
1
T (n) = T ( 𝑛 𝑘𝑛 ) +x
Base case:
1
𝑛 𝑘𝑛 =a
1
log 𝑎 𝑛 = log a
𝑘𝑛
log 𝑘 𝑛 = kx
= log 𝑘 log 𝑎 𝑛 = x
 Θ (logklogan)

Q103. 𝑇
𝑘
𝑛 + log 𝑛 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 𝑎
(a) Θ (logklogan) (b) Θ (log n logklogan)

(c) Θ (log 𝑛) (d) Θ (logalogkn)

Answer: c
Solution:
𝑘
𝑇 𝑛 + log 𝑛 ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 𝑎
1/k
T (n) = T (n ) + log n - - - - - - (1)
1 1
T (n1/k) = T (𝑛 𝑘2 ) + log n - - - - (2)
𝑘
putting eq (2) in eq (1)
1 1
T (n) = T (𝑛 𝑘2) + log n + log n
𝑘
𝑛 1 1 1 1
T (n) = T (𝑛 𝑘𝑥 ) + log n [ 1+ + + + …+ ]
𝑘 𝑘2 𝑘3 𝑘 2−1
1 1
(𝑛 𝑘𝑥 ) =a, log 𝑎 𝑛 = logaa
𝑘𝑥
logk logan = x
(ADA) Page 42
 (𝑟 𝑛 − 1)
1
1−( )𝑥 𝑎 𝑖𝑓 𝑟 > 1
𝑟−1
= log n [ 𝑘
1 ] GP sum ( 1−𝑟 𝑛 )
1−
𝑘 𝑎 𝑖𝑓 𝑟 < 1
1−𝑟
1
1−( )log 𝑘 log 𝑎 𝑛
= log n 𝑘
1
1−
𝑘

(log 𝑎 𝑛)−1 log 𝑛 log 𝑎 𝑛−1

= log n 1 − 1 = 1
1− log 𝑎 𝑛 1−
𝑘 𝑘
= ⋍  (log n)
Q104. 𝑇 𝑛 − 1 + 𝑇 𝑛 − 2 + 1; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 1; 𝑖𝑓𝑛 = 1
0; 𝑖𝑓𝑛 = 0
n
(a) O (2 ) (b)O (n2)
(c)O(n log n) (d)O (n)

Answer: A
Solution:
𝑇 𝑛 − 1 + 𝑇 𝑛 − 2 + 1; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 1; 𝑖𝑓𝑛 = 1
0; 𝑖𝑓𝑛 = 0

2𝑘+1 − 1
20 + 2 1 + 2 2 + . . . . . + 2k =
1
= 2n+1 –1
k=n
= Θ(2n).
Q105. 𝑛 3𝑛
𝑇 +𝑇 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4 4
1; 𝑖𝑓𝑛 = 1

(ADA) Page 43
 (a) Θ (n) (b) Θ (𝑛 𝑛)
(c) Θ (𝑛 log log 𝑛) (d) Θ (n log n)

Answer: D
Solution:
𝑛 3𝑛
𝑇 +𝑇 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4 4
1; 𝑖𝑓𝑛 = 1

3
= ( )k n = 1
4
4
n = ( )k
3
Θ (n log 4 𝑛)
3
k = log 4 𝑛
3
Θ (n log n)
Q106. 𝑛 𝑛 𝑛 𝑛 𝑛 𝑛
𝑇 + 𝑇 +𝑇 +𝑇 +𝑇 +𝑇 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2 4 8 16 32 32
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ (𝑛2 )
(c) Θ (𝑛 log log 𝑛) (d) Θ (n log n)

Answer: d
Solution;
𝑛 𝑛 𝑛 𝑛 𝑛 𝑛
𝑇 + 𝑇 +𝑇 +𝑇 +𝑇 +𝑇 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 2 4 8 16 32 32
1; 𝑖𝑓𝑛 = 1
Θ (n log n)
Q107. 𝑇 0.49𝑛 + 𝑇 0.51𝑛 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ (𝑛2 )
(c) Θ (𝑛 log log 𝑛) (d) Θ (n log n)

(ADA) Page 44
 Answer: d
Solution;
𝑇 0.49𝑛 + 𝑇 0.51𝑛 + 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 =
1; 𝑖𝑓𝑛 = 1
49 54
T (n) = T ( 𝑛) + T ( n) + n
100 100

49 2
= 𝑛 =1
100
49
n=( )k
100
k = log 100 𝑛
49

 overall complexity Θ (n log 100 𝑛)

49

Q108. 𝑛
64 𝑇 + 𝑛! ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ (𝑛3 )
(c) Θ (𝑛 log log 𝑛) (d) Θ (n!)

Answer: d
Solution:
𝑛
64 𝑇 + 𝑛! ; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 4
1; 𝑖𝑓𝑛 = 1
=𝑛 log 𝑏 𝑎
=𝑛 log 4 64
= n < n!
Θ (n!)

(ADA) Page 45
 Q109. 𝑛
8𝑇 + log 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 8
1; 𝑖𝑓𝑛 = 1
(a) Θ (n) (b) Θ ( 𝑛)
(c) Θ (𝑛 log log 𝑛) (d) Θ (n log n)

Answer: b
Solution:
𝑛
8𝑇 + log 𝑛; 𝑖𝑓𝑛 > 1
𝑇 𝑛 = 8
1; 𝑖𝑓𝑛 = 1
= 𝑛log 𝑏 𝑎 = 𝑛log 8 8 = n1/2 = Θ ( 𝑛)
Q110. Consider the recurrence relation an=7an−1−10an−2with a0=2 and a1=3.Which of the
following is the exact solution of this recurrence relation?
7 −1
(a) 2.2n + 3.5n (b) (2)𝑛 + (5)𝑛
3 3
7 −1 7 1
(c) (5)𝑛 + (2)𝑛 (d) (2)𝑛 + (5)𝑛
3 3 3 3

Answer: B
Solution:
an = 7an – 1 – 10an-2
 x2 = 7x – 10
 x2 – 7x + 10 = 0
 (x – 2) ( x – 5) = 0
 x = 2, 5
Since both roots are distinct
hence solution will be
an =  (x1)n +  (x2)n
 an = . 2n +. (5)n - - - -(1)
given that a0 = 2, a1 = 3
If n = 0, then a0 =  +    +  = 2 - - - -(3)
If n = 1 then a1 = 2 + 5  2 + 5 = 3 - - - -(4)
(3)  2 – (4)  2 + 2 - 2 - 5 = 4 – 3
 - 3 = 1   = -1/3
  = 2 -  = 2 + (-1/3) = 7/ 3
now, from (1) an = 7/3 (2)n + (-1/3) (5)n
 Answer will be B

Q111. Consider the recurrence relation an=6an−1−9an−2 with initial

conditions a0=1 and a1=4.Which of the following is the exact solution of this recurrence

(ADA) Page 46
 relation?
(a) 3n + 1 (b)3𝑛−1 (𝑛 + 3)
(c)(b) 3𝑛 (𝑛 + 3) (d)(b) 3𝑛−1 (𝑛 − 3)
Answer: b
Solution:
an = 6an-1 – 9an-2
 x2 = 6x – 9
 x2 – 6x + 9 = 0
 (x – 3)2 = 0  x = 3, 3
since roots are real and equal
hence an =  𝑥1𝑛 +  n 𝑥1𝑛
 an =  3n +  n3n - - - -(1)
given that a0 = 1, a1 = 4
If n = 0, a0 =  = 1
If n = 1, a1 = 3 + 3 = 4
 3 (1) + 3  = 4
 3 = 1
  = 1/3
 an = 3n + 1/ 3. n. 3n
 an = 3n + n .3n – 1 = 3n-1 [n + 3]

Data for next two questions: Consider the recurrence relation an = 5an–1 – 6an–2
Q112. What sequence do you get if the initial conditions are a 0 = 1, a1 = 2?
(a) 1, 2, 4, 6, 8, ….. (b) 1, 2, 4, 8, 16, 32, …..
(c) 1, 2, 4, 7, 12, 18, ….. (d) 1, 2, 3, 4, 5, 8, 7, 16…..

Answer: b
Solution;
an = 5an-1 – 6an -2
 x2 = 5x – 6
 x2 – 5x + 6 = 0
 (x – 2) (x – 3) = 0
 x = 2, 3
Since roots are distinct hence,
an =  . (2)n +  (3)n - - - - -(1)
given that a0 = 1, a1 = 2
 a0 =  +    +  = 1 - - - - -(2)
a1 = 2 + 3  2 + 3 = 2 - - - -(3)
(1)  2 – (3)

(ADA) Page 47
  2  + 2 - 2 -3 = 2 – 2
-=0
=0
and  = 1 (from (2))
an = 1. 2n + 0 (3)n
 a n = 2n
 sequence of this recurrence relation = 1, 2, 4, 8 , 16, 32 . . .
Answer is B.
Q113. Which of the following is a closed formula for this sequence?
(a)2n+1 – 1 (b)2n+1+ 1
(c)2n+1 (d)2n

Answer: d
Solution:
Discussed in above
Q114. Which of the following is correct recurrence relation with proper initial conditions
for sequence1,5,17,53,161,485….?
(a)an = 3an-1 + 1 with a0 = 1 (b)an = 2an-1 + 1 with a0 = 2
(c)an = 3an-1 + 2 with a0 = 1 (d)an = 2an-1 + 2 with a0 = 1

Answer: c
Solution:
sequence1, 5, 17, 53, 161, 485
we select option c
an = 3an – 1 + 2
a0 = 1, a1 = 3. a0 + 2 = 3. (1) + 2 = 5
a2 = 3a1 + 2 = 3  5 + 2 = 17
a3 = 3a2 + 2 = 3  17 + 2 = 53
.
.
and so on
 It is correct and other options are incorrect.
Q115. Which of the following is a closed formula for above sequence?
(a) 2.3n-1 – 1 (b)2.3n – 1
(c)2.3n-1+ 1 (d)2.3n – 3n – 1
Answer: b
Solution:
an = 3an – 1 + 2, a0 = 1
a1 = 3a0 + 2 = 3(1) + 2 = 5
a2 = 3a1 + 2 = 3  5 + 2 = 17
(ADA) Page 48
 So sequence is a0, a1, a2 . . . . an
Let S = a0 + a1 + a2 + an – 1 + an
 S = 1 + 5 + 17 + 53 + 161 + . . . .an-1 + an
S= 1 + 5 + 17 + 53 + 161 + . . . .an-1 + an
0 = 1 + {4 + 12 +36+ 108 +324 + . . .}- an
 an = 1 + a {1 + 3 + 32 + 33 + . . . 3n-2}
an = 1 + 4 { 30 + 31 + 32 + . . . 3n-2}
3𝑛 −1 − 1
=1+4[ ]
3−1
= 1 + 2 [3n-1 – 1] = 1 + 2 .3n-1 – 2
= 2.3n-1 – 1
Q116. Use iteration to solve the recurrence relation an=an−1+n with a0=4.Which of the following
is the exact solution of this recurrence relation?
𝑛(𝑛+1) 𝑛(𝑛+1)
(a) +4 (b) −4
2 2
𝑛(𝑛−1) 𝑛(𝑛−1)
(c) +4 (d) −4
2 2
Answer: A
Solution:
an = an – 1 + n; a0 = 4
T (n) = T (n – 1) + n
= T (n – 2) + (n – 1) + n
= T (n – 3) + (n – 2) + (n – 1) + n
.
.
= T ( n – k) + n – (k – 1) + n - (k -2 ) + . . . (n -2) + (n – 1) + n
[Let n – k = 0  n = k]
 T (n) = 4 + { 1 + 2+ 3 + . . . (n -2) + (n – 1) + n]
𝑛 (𝑛+1)
=4+
2
Answer : A
Q117. What will be the complexity of the following function?
int p(int n)
{
int r = 1;
for(i= 1; i<=n; i= i+2)
for(j= 1; j<=n; j=j*2)
while(r <= j)
r := r + 1;
return r;
}
(a)𝜃((𝑛2 ) (b) 𝜃(𝑛 log 𝑛)
(c) 𝜃(𝑛 log 𝑛)
2
(d) 𝜃(𝑛 (log 𝑛)2 )

(ADA) Page 49
 Answer: b
Solution;
j = 1 runs for 1 times
j = 2 r runs for 1 times
j = 4 r runs for 1 times
j = 8 r runs for 1 times
j = log n r runs for 1 times
for i = 1 r runs for log n times
for i = 2 j runs for log n times but r doesn‟t runs
for i = 3 j runs for log n times but r doesn‟t runs
.
.
.
for i = n j runs for log n times
 overall complexity 𝜃(𝑛 log 𝑛).
Q118. What will be the complexity of the following function?
int p(int n)
{
int r;
for(i= 1; i<=n; i= i+2)
for(j= 1; j<=n; j=j*2)
{
r = 1;
while(r <= j)
r := r + 1;
}
return r;
}
(a)𝜃(𝑛2 ) (b) 𝜃 𝑛 log 𝑛
(c) 𝜃 𝑛 log 𝑛
2
(d) 𝜃 𝑛 (log 𝑛)2

Answer: a
Solution:
j = 1 r runs for 1 time
j = 2 r runs for 2 times
j = 4 r runs for 4 times
j = log n r runs for log n times
 for i = 1 r runs for (20 + 21 . . . 2k) = 2k+1 -1 =n
for i = 3 r runs for n times
.
.
(ADA) Page 50
 similarly i runs n/2 times & r runs for n times  complexity is 𝜃(𝑛2 )
Q119. What will be the complexity of the following function?
int p(int n)
{
int r;
for(i= 1; i<=n; i= i+2)
r = 1;
for(j= 1; j<=n; j=j*2)
{
while(r <= j)
r := r + 1;
}
return r;
}

(a)𝜃 𝑛2 (b) 𝜃 𝑛 log 𝑛

(c) 𝜃 𝑛2 log 𝑛 (d) 𝜃 𝑛

Answer: d
Solution:
loop i runs for n/ 2 times
loop j runs for logn times
But for loop of i ends before the that of loop j
 complexity of code is 𝜃 𝑛
Q120. How many times L4 will run by the following function in terms of n exactly?
void p(int n){
int r = 0;
for(i= 1; i<=n; i++) // L1
{
for(j= 1; j<=n; j++) // L2
for(k= j; k<=i+j; k++) // L3
r = r + 1; //L4
}
return r ;
}
𝑛 𝑛+3
(a)𝑛3 (b)
2
𝑛 2 𝑛+3 𝑛(𝑛+1) 𝑛+3
(c) (d)
2 2

Answer: c
Solution:
j=1

(ADA) Page 51
 j = 1 k= 1 to 2 2 times
j = 2 k = 2 to 3 2 times
j = 3 k = 3 to 4 2 times
j = n k = n to n + 1 2 times
 k runs for overall 2n times
i=2
j = 1, k = 1 to 3 = 3 times
i=n j=1
k = 1 to n+1 = n+1 times
k = 2 to n+2 = n+1 times
k runs overall for (n + 1) n
 n [ 2 + . . .T (n + 1)]
𝑛+2 𝑛+3
= n.n = n2
2 2
Q121. What is the running time of the following function?
void Function (int n)
{
int a =1, b = 0, s = 1;
for(a = 1; a<=n; a = a+2)
{
b =1;
while(s <= n)
{
b++;
s = s+ b;
}
}
(a) 𝜃(log 𝑛) (b)𝜃( 𝑛)
(c)𝜃(𝑛 𝑛) (d)𝜃(𝑛)

Answer: d
Solution:
for a while loop runs for ( 𝑛) time
(1 + 2 + 3 + . . .+ k) < n
𝑘 (𝑘+1)
= <n
2
22 < n
k< 𝑛
 s=n
now while loop shouldn‟t run for a = 3 while loop doesn‟t run
.
.

(ADA) Page 52
 for loop runs n/2 time
complexity  (n + 𝑛) +  (n)

For next two questions: Consider the following code

s = 0;
c = 0;
for(i= 1; i <=n; i++)
for(j= 2*i; j<=2*n; j++)
{
s =s + 1;
c =c + s;
}
Q122. What is the value of „s‟ in terms of n after completion of this code?
𝑛 𝑛+1 2𝑛 +1 𝑛 𝑛+1 𝑛−1
(a) (b)
6 2
2
(c)𝑛 − 𝑛2
(d)n
Answer: d
Solution:
i=1
j = 1, 2, 3, 4, 5, . . . 2n
s = 1, 2, 3, . . .2n-1
 find the value of s = 2n -1
i = 2, j = 4, 5, 6, 7. . . 2n
final value of 5 = (2n – 1) + (2n – 3)
i = 3 j = 6, 7, 8, 9, 10 . . .2n
final value of s = (2n – 1) + (2n – 3) + (2n – 5) ….+ 3 +1
i = n, j = 2n . . . .
 final value of s
(2n -1) + (2n – 3) + (2n – 5) + ….3 + 1
= n/2 [2n – 1 + 1]
= n/2  2n
= n2
Q123. What is the value „c‟in terms of n after completion of this code?
1
(a) (𝑛2 − 𝑛)(𝑛2 − 𝑛 + 1) (b) n2
2
𝑛 2 (𝑛 2 +1)
(c)𝑛2 − 𝑛 (d)
2
Answer: d
Solution:
i = 1, j = 2, s = 1, c = 0 + 1 = 1
j = 3, s = 2, c = 1 + 2

(ADA) Page 53
 j = 4, s = 3, c = 1 + 2 + 3
.
.
.
j = 2n, s = 2n – 1, c = 1 + 2+ 3 +. . . (2n – 1)
i = 2, j = 4, s = 2n, c = 1 + 2 + 3 + . . .(2n + 1)
j = 5, s = 2n + 1, c = 1 + 2+ 3. . .(2n + 1)
.
.j= 2n, s= (2n-1)+(2n-3) ,c =1+2+3+…….4n-4.
.
i = n, j = 2n, s = n2
 C = 1 + 2+ 3 + . . . n2
𝑛 2 (𝑛 2 + 1)
=
2
Answer is d.

For the next two questions:

void f(int n, int a, int b)
{
if (n>0)
{
f(n-1, a, b);
printf("%d%d",a,b);
f(n-1, b, a);
}
}
Q124. What is the time complexity of code given above?
(a) θ (2n) (b) θ (logn)
(c) θ (n) (d) θ (n2)

Answer: a
Solution:
T (n) = 2T (n – 1) + 1
 Complexity is θ (2n)
Q125. What is the space complexity of code given above?
(a) θ (2n) (b) θ (logn)
(c) θ (n) (d) θ (n2)

Answer: c
Solution:

(ADA) Page 54
  Overall spare complexity is θ (n)
Q126. What will be the output if 𝑓(3, 3, 2) is called?
(a) 32322332232332 (b) 32322332233232
(c)23322332232332 (d) error

Answer: a
Solution:

Output = 32322332232332
Q127. How many times L4 will run by the following function in terms of n exactly?
void p(int n){
int r = 0;
for(i= 1; i<=n; i++) // L1
{
for(j= 1; j<=n; j++) // L2
for(k= 1; k<=i+j; k++) // L3
r = r + 1; //L4

(ADA) Page 55
 }
return r ;
}
𝑛 2 (𝑛+1) 𝑛 𝑛+1 2
(a) (b)
2 2
𝑛 𝑛+1 (2𝑛+1)
(c) n2(n+1) (d)
6
Answer: c
Solution:
for i = 1 N.o of times r runs
j = 1 k runs 1 to 2 = 2
j = 2 k runs from 1 to 3 = 3
1 to n + 1 = n + 1
𝑛 (𝑛+3)
Total times r runs [ ]
2
for i = 2, j = 1, k runs from 1 to 3 = 3
1 to 4 = 4
1 to n + 2 = n + 2
𝑛
Total time r runs  (n + s)
2
for i = n, j = 1, k runs from 1 to n +1, n + 1 n+ 1
n+2
1 to a. n + n = n + n
𝑛 (𝑛+1) 𝑛 2 +𝑛 𝑛 (2𝑛+1)
Total time r runs  n2 + = n2 + =
𝑛2 2 2
𝑛
overall complexity [(n + 3) + (n + 5) . . . (3n + 1)]
2
𝑛 𝑛+4 2
= n [( )] = n [ n + 1]
2 2
Q128. What is the running time of the following code?
int x = 0;
for (int i = 0; i < n; i = i+1)
{
if (x < i) x = x+1;
else i = n + x;
}
(a) O(1) (b) O(n)
(c) O(n2) (d) O(n3)

Answer: a
Solution:
X=0
For i = 0; if (x < 0) condition false
now i = n

(ADA) Page 56
  complexity O(1)

Q129. How many times does the following code print out “India”?
for( int i = 1; i < n – 1; i = i + 3 )
for( int j = 1; j <n; j = j * 3 )
for( int k = 3*n; k > 0; k-- )
for( int m = 0; m < 1000; m++)
printf(“India”);
(a) Θ(n2log(n) ) (b) Θ(nlog(n)2)
(c) Θ(n3) (d) Θ(n4)

Answer: A
Solution:
loop i runs for n/3 times nearly loop j runs for log 3 𝑛 times.
Loop k runs for 3n times
Loop m runs for 100 times .
𝑛
1000   log 3 𝑛  3n
3
= O (100n2 log 3 𝑛)
= O (n2 log n)
Q130. What is the tightest running time of the function in terms of n?
void f(int n) {
int a = 0, x = 2;
while (n> 1) {
if (n % x == 0) return a + n;
n =n/2;
}
return a;
}
(a) O(1)
(b) O(log n)
(c) O(n)
(d) O(n2)

Answer: b
Solution:
While loop runs for log n times.
Q131. What is the running time of the function?
for (i=1; i<=n*n; i++)
for (j=0; j<i; j++)
printf(“*”);

(ADA) Page 57
 (a) O(n)
(b) O(n2)
(c) O(n3)
(d) O(n4)

Answer: d
Solution:
For i = 1, j runs for 1 times
For i = 2, j runs for 2 times
for i = n2, j runs for n2 times
 overall times j runs = 1 + 2 + 3 . . . n2
𝑛 2 (𝑛 2 + 1)
= =  (n4)
2
Q132. For the following pseudo-code, what is the -notation of its running time if the time
required for
evaluating f (n) is (n2).
i= 0;
while (i < f (n))
{
sum = sum + f (i) ;
i = i + 1;
}
(a) (n2) (b) (n4)
(c)(n6) (d) ((f(n))4)

Answer: c
Solution:
 complexity of f (n) = n2
while ( i = n2)
{
sum = sum + i2
i=i+1
}
12 + 22 + 32 + 42 + 52 + . . . n2+ . . . +n4
𝑛 2 𝑛 2 +1 2𝑛 2 +1
= = n6
6

Q133. Consider the following code:

for (i = 0; i < n; i = i + 2) {
for (j = 1; j < n; j=j*2) {
for (k = 1; k < 1000; k=k*5) {

(ADA) Page 58
 printf(“Hari”);
}}
for (j = 0; j < n; j=j+ 2) {
printf(“Bol”);
}}
What is the running time complexity of above code?
(a) (n2) (b) (n logn)
(c)(n )3
(d) (n2log n)

Answer: b
Solution:
Loop i runs for n/2 times
j runs for log n times
𝑛
overall complexity is (n logn + ) = (n logn)
2

Q134. Consider the following code segment:

for ( int i = 0; i < n; i++){
for ( int j = 0; j < i; j++) sum++;
for ( int k = 0; k < n*n; k++) sum++;
for(int m = 0; m<i; m = m*2) sum++;
}
What is the running time complexity of above code?
(a) (n2) (b) (n3logn)
(c)(n3) (d) (n4)

Answer: b
Solution:
For i = 0, j runs for 0 times; k runs for n2
i = 1, j runs for 1 time k runs for n2
i = 2, j runs for 2 times k runs for n2 log2 time
i = n, j runs for n times k runs for n2 log n time
 Overall complexity (n3logn)
Q135. Consider the following code segment:
for ( int i = 0; i < n; i ++)
for ( int j = 1; j < n*n*n; j=2*j)
printf(“Be always happy”);
What is the running time complexity of above code?
(a) (n2) (b) (n logn)
3
(c)(n(log n) ) (d) (nloglogn)

(ADA) Page 59
 Answer: b
Solution:
Loop i runs for n times
Loop j runs for log n3 times = 3 log n
 overall complexity = (n logn)
Q136. Consider the following code segment:
for (i = 1; i<=n; i++)
{
for (j = 2*i; j<= n;
j++)
s = s+1;
}
What is the running time complexity of above code?
(a) (n2) (b) (n logn)
(c)(n )3
(d) (1)

Answer: A
Solution:
For i = 1 j runs from 2 to n = (n – 1)
i = 2 j runs from 4 to n = (n – 3)
for i = n/2, j runs from n to n = 1
 overall complexity = 1 + 3 + . . . (n – 3) + (n – 1)
𝑛 (𝑛−1+1) 𝑛2
= = (n2)
2 2

Q137. Consider the following code segment:

for (i = 1; i<= n; i++)
{
j = i;
while (j < n)
j = 2*j;
}
What is the running time complexity of above code?
(a) (n2) (b) (n log n)
(c)(n) (d) (n 𝑛)

Answer: c
Solution:
i = 1, j= 1 while loop runs for log n times.
i = 2, j = 2

(ADA) Page 60
 2, 4 …2k.. n 2k – 1 < n
while loop runs for log n/2 times
j = 3 3, 6, 12, 24 . . . < n
3[20+21+22+23+….2k] <n
 It runs for log2 n/3 times
j = 4 It runs for log n/4 times
j = n It runs for log n/n times
 complexity = log n + log n/2 + log n/3 + . . . log n/n
𝑛𝑛
= log  (n)
𝑛!

Q138. Consider the following code segment:

for i = 1 to n do
j=n
while i*i <j do
j=j–1
end for
What is the running time complexity of above code?
(a) (n2) (b) (n log n)
3/2
(c)(n ) (d) (1)

Answer: c
Solution:
i = 1 to n, let n = k2
i = 1, j = n, n-1, n-2. . .4, 3, 2  (n – 1)2
i = 2, j = n, n-1, . . .5  (n – 22)
i = 3, j = n, n- 1, . . .10  (n – 32)
i = k, j = n, n-1. . . (n – k2)
Total number of comparison
= (n -12) + (n – 22) + ( n – 32) + . . . (n – k2)
= n.k – {12 + 22 + 32 + . . . k2}
𝑘 𝑘+1 (2𝑘+1)
= n.k –
6
𝑘 [6𝑛 −2𝑛−3𝑘−1
= = 𝑛 [ 6n – 2n – 3 𝑛 - 1]
6
= 4n 𝑛 - 3n - 𝑛 =  (n 𝑛) =  (n3/2)
Q139. Consider the following code segment:
for i = 1 to n do
j=2
while j ≤ n do
j = j*j

(ADA) Page 61
 end for
What is the running time complexity of above code?
(a) (n2) (b) (log logn)
(c)(n) (d) (nlog (logn))
Answer: d
Solution:
for i = 1, j = 2 , 2 = 22 (22) . . . 22 < n
2k = log n
k = log log n
for i = 2 j runs for log log n
 complexity = n log log n
Q140. How many times the following loop runs for given value of n?
for(int i=2 ; i<=n ; i=pow(i,2)){
printf("%d",i);
}
What is the running time complexity of above code?
(a) O(n) (b) O(log n)
(c) O(loglog n) (d) O(sqrt(n))

Answer: c
Solution:
2 𝑘
2, 22, 22 , . . . 22
𝑘
= 22 < n
2k < log n
k = log log n
 complexity O(loglog n)
Q141. Consider the following code segment. Assume n to be a positive integer.
for(i=1; i<=n; i++) {
for(j=1; j<=n; j=j+i)
{ printf(“Zeal”); } }
What is the running time complexity of above code?
(a) (n2) (b) (n log n)
(c) (n) (d) (n log (log n))

Answer: b
Solution:
i = 1, j runs for n times
i = 2, j runs for n/2 times
i = 3 j runs for n/3 times

(ADA) Page 62
 .
.
.
i = n, j runs for n/n times
n [ 1 + ½ - 1/ 3 + . . . 1 /n] = n log n
Data for next two questions: Consider the following code:
int g(int n) {
if (n == 1)
return 2;
else
return 3 * g(n / 2) + g( n / 2) + 5;
}
Q142. What is time and space complexity of the above code?
(a) Time= O(nlogn), Space=O(n) (b) Time= O(nlogn), Space=O(logn)
(c) Time= O(n), Space=O(n) (d) Time= O(n), Space=O(logn)

Answer: d
Solution:
G (n) = 2 G (n/2) + 1
O (𝑛log 2 3 ) = O (n) time complexity
Space complexity =

𝑛
= 𝑘 =1
2
k = log n
Q143. What will be the recurrence relation of given code for n>1?
(a) T(n) = 3 T(n/2) + 1 (b) T(n) = 4T(n/2) + 5
(c) T(n) = 2 T(n/2) + 1 (d) T(n) = T(n/2) + 1

Answer: c
Solution:
T (n) = 2 T (n/2) + 1
 2 times because function is called
Data for Next two questions: Consider the following function:
long power (long x, long n) {
if(n == 0)
(ADA) Page 63
 return 1;
else if(n == 1)
return x;
else if ((n % 2) == 0)
return power (x, n/2) * power (x, n/2);
else
return x * power (x, n/2) * power (x, n/2);
}
Q144. What is worst case time and space complexity of the given code?
(a) Time= O(nlog n), Space=O(n) (b) Time= O(nlogn), Space=O(logn)
(c) Time= O(n), Space=O(n) (d) Time= O(n), Space=O(logn)

Answer: d
Solution:
T (n) = 2T (n/2) + 1
Time complexity < O (n)
space complexity = O (log n)
Q145. What will be the recurrence relation of above code for n>1?
(a) T(n) = 3 T(n/2) + 1 (b) T(n) = 4T(n/2) + 5
(c) T(n) = 2 T(n/2) + 1 (d) T(n) = T(n/2) + 1

Answer: c
Solution:
Same as Q144.
Data for Next two questions: Consider the following function:
void F(int n) {
If (n==0) return 1 ;
If (n % 2 = = 1) Return (2*F(
n/2 ));
return (n+1)
}
Q146. What is the best case and worst case time complexity of the given function?
(a) O(1) and O(log2n) (b) O(1) and O(nlogn)
(c) O(log2n) and O(log2n) (d) O(n) and O(n)

Answer: a
Solution:
T (n) = T (n/2) + 1
best case O (1)
worst case O (log n)
Q147. What will be the recurrence relation for above code?
(a) T(n) = T(n/2) + n (b) T(n) = 2T(n/2) + n
(ADA) Page 64
 (c) T(n) = 2T(n/2) + 1 (d) T(n) = T(n/2) + 1

Q148. The best big-O of n and m for the number of additions in this code is:
sum = 0
for ( x = 0 ; x <sqrt (2n) / 2 ; ++x )
for ( y = x ; y < x + m; ++y )
for ( z = y ; z < y + m; ++z )
sum = z + sum
(a) O(nm2) (b) O( 𝑛m2)
2 2
(c) O(n m ) (d) O(n2log n)

Answer: b
Solution:
x = 0 y runs for n time & z runs for m time
 for x = 0 or y & z runs for m2 time
x runs for 𝑛 times
 overall complexity is O( 𝑛m2)
Q149. What is the time complexity of the following code?______________
i =1
k =1
while (i < n){
i =i + k
k =k + 1
}
(a) (n2) (b) (log log n)
(c) (n) (d) ( 𝑛)

Answer: d
Solution:
while loop runs for
i = 1, k = 1 (1 < n)  i = 2, k = 2
i = 2, k = 2 (2 < n)  i = 1 + 2; k = 3
i = 3, k = 8 (3 < n)  i > 1 + 2 + 3, k = 4
I = 2 – 1, k = x – 1, (x – 1 < n), i= 1 + 2 + 3 . . . x k= x
 (1 + 2 + 3 . . .+ x) 4n
𝑥 (𝑥+1)
= n
2
x n
2

x 𝑛
 overall complexity is ( 𝑛)
Q150. What is the asymptotic complexity of the function f ( ) below when h (n) = 3log n,
g (n) = 4n0.45
f(n) {
g(n);
h(n);
(ADA) Page 65
 }
(a) (log n) (b) (n0.45)
(c) (n0.45log n) (d) none of these

Answer: b
Solution:
h (n) = 3 log n
g (n) = 4n0.45
 Overall complexity is (n0.45).
Q151. What is the time complexity of the following code using big-O notation?
int f2 ( int N )
{
int x = 1;
while ( x < N )
x = x * 3;
return x ;
}
void main() {
int x = 0 , i ;
for ( i = 0; i < N ; i ++)
x += f2 ( N );
}

(a) (NlogN) (b) (N2)

(c) (N2logN) (d)none

Answer: a
Solution:
The series will be log1 + log2 + log 3 + log 4 . . . + log N
= log 1.2.3 . . .(N – 1)
= log (N-1)!
= (n – 1 ) log N – 1
 overall complexity = (N log N)
Q152. What is the time complexity (in big-O notation) of the following recursive code?
int fun(int n) {
if (n <= 2) return n;
int sum = 0;
for (int j=1; j<n; j *= 3)
sum += j;
for (int k=n; k>1; k /= 3)
sum += k;

(ADA) Page 66
 return fun(n – 1) + sum;
}
(a) O(nlog2n) (b) O(n2logn)
(c) O(nlogn2) (d)none of these

Answer: c
Solution:
Loop j runs for logn times
loop k runs for logn times
T (n) = T (n – 1) + 2 log n
T (n – 1) = T (n – 2) + 2 log (n – 1)
T (n) = T (n – 2) + 2(log n – 1 log (n – 1) + . . .log (n – 1 ))
k = (n – 2)
T (2) + 2 [log n + . . .+ log2]
2 log n!
 complexity O(nlogn2)
Q153. Consider the following recursive code
int f(int n){
if (n==0) return 0;
else if (n==1) return 1;
else{
int val = 2*f(n-1);
val = val - f(n-2);
val = val - f(n-2);
return val;
}
}
What is the returned value of f (9)? ______________

Answer: 16
Solution:

(ADA) Page 67
(ADA) Page 68
(ADA) Page 69
 Q154. Consider the following function:
int f (int n){
if (n==0) return 0;
else if (n==1) return 1;
else{
int val = 2*f (n-1);
val = val - 2*f (n-2);
val += 1;
return val;
}
}
Let f(n) be the value returned by the function f(int) when given input n. The recurrence
relation for f(n) will be
(a) f(n) = 2f(n - 1) - 2f(n - 2) + 1 (b) f(n) = f(n - 1) + f(n - 2) + 1
(c) f(n) = 4f(n - 1) - 4f(n - 2) + 1 (d) f(n) = f(n - 1) - f(n - 2) + 1

Answer: A
Solution: f (n) = 2f (n – 1) – 2f (n – 2) + 1
Q155. Which recurrence relation describes the worst-case running time of the following
algorithm as a function of n
int Foo(int A[], int first, int n) {
if (n < 4) return n + 1;
i =0;
sum =0;
while (i*i < n) {
sum =sum + A[i * i];
i = i + 1;
}
j =1;
B =new array;
while (j < n) {
append A[j] to B
j =2 * j }
x =Foo(A, first + n/4, n/2)
return x * sum * Foo(B, 0, length[B])
}
1; 𝑖𝑓𝑛 < 4
(a)T(n) = 𝑛
𝑇 + 𝑇 log n +  n ; 𝑖𝑓𝑛 ≥ 4
2
n
T + T logn + logn ; if n ≥ 4
(b) T(n)= 2
θ 1 ; if n < 4

(ADA) Page 70
 n
T + T logn + 1; if n ≥ 4
(c) T(n)= 2
θ 1 ; if n < 4

(d) None of these

Answer: A
Solution:
1; 𝑖𝑓𝑛 < 4
T(n) = 𝑛
𝑇 + 𝑇 log n +  n ; 𝑖𝑓𝑛 ≥ 4
2
Q156. What is the tightest Big-O analysis of the following code segment?
for (int i = 1; i < n; i = i*3)
for (int j = 0; j < i; j++)
Sum = Sum + i * j;
(a) O(log n) (b) O(n) (c) O(n log n) (d) O(n2 )
Answer: b
Solution:
i = 1, j runs for 1 times
i = 3, j runs for 3 times
i = a, j runs for 4 times
i = 3k, j runs for 3k times
3k = n  k = log n
30 + 31 + 32 + . . . 3k times
3𝑘+1 −1
= = O (n)
2
Q157. Refer to the following method.
int recur(int n) {
if (n==0 ||n== 1 )
return 1;
else if ( n == 3 )
return 3;
else
return recur( n - 1) + recur( n - 2);
}
How many times is recur (3) called as a result of calling recur( 7) ? ________

Answer: 5
Solution;
Rec (7)

Rec (6) + Rec (5)

Rec(5) + Rec (4) Rec (4) + Rec (3)

(ADA) Page 71
 Rec (4) + Rec (3) Rec(3) Rec (3) Rec (3) + Rec (2)

Rec (3) Rec (2)

Q158. Consider the following code

int foo(int n, int a, int d) {
if (n == 1)
return a;
else
return d * foo(n/2, a, d);
}
What value is returned by the call foo (9, 6, 2)? ____________

Answer: 48
Solution:
foo (4, 6, 2)

2 * foo (4, 6, 2) = 2 * 24 = 48

2 * for (2, 6, 2) = 2 * 12

2 + foo (1, 6, 2) = 2 * 6 = 12

Q159. Consider the following recursive program.

//n is any positive integer //m is a positive integer between 2 and 9
void fun(int n, int m){
if (n<m)
printf(“%d”,n);
else {
fun(n/m, m); printf(“%d”, n%m);
}
}
What is the output for fun(21, 6)?_________
Answer: 33
Solution:
f (2, 6)

f (3, 6) P + (3)

(ADA) Page 72
 Pf (3)

Q160. Consider the following code

int f(int k, int n)
{
if (n == k)
return k;
else
if (n > k)
return f(k, n - k);
else
return f(k-n, n);
}
What value is returned by the call f (8, 10)? __________

Answer: 2
Solution:
f (8, 10)

f (2, 8)

f (2, 6)

f (2, 4)

f (4, 2)
return = 2

Q161. Consider the following code

void doSomething(int n)
{
if (n > 0) {
doSomething(n - 1);
printf(“%d”,n);
doSomething(n - 1);
}
}
What would be output following the call do Something(4)? ______________
(a) 121312141213121 (b) 121312411213121
(c) 121213131212141 (d) 141212131312121

Answer: a
(ADA) Page 73
 Solution:

answer is 121312141213121
Q162. Consider the following code
int fl(int a, int b)
{
if (a == b)
return b;
else
return a + f2(a - 1, b);
}
int f2 (int p, int q)
{
if (p < q)
return p + q;
else
return p + f1(p - 2, q);
}
What value will be returned by a call to f1(8, 5)? _________

Answer: 20
Solution:

 f1 (5, 5) = 5

(ADA) Page 74
 Q163. Consider following code:
int foo(int x) {
if (x == 1 ||x == 3)
return x;
else
return x * foo(x - 1);
}
Assuming no possibility of integer overflow, what will be the value of z after execution of
the following statement?
int z = foo(foo(3) + foo(4));
(a) (15!)/(2!) (b) 3! + 4!
(c) (7!)! (d) (3! + 4!)!

Answer: a
Solution:
z = foo (foo (3) + foo (4)
foo (3) = 3
foo (4) = 4. f (3)
= 4.3 = 12
z = foo (15)
15 * foo (14)

14 * foo (13)  3  4  5  6  7  8  9  10  11  12  13  14  15
15!
 =
2!
4 * foo (3)  foo (3) = 3

(ADA) Page 75