Birla Institute of Technology and Science-Pilani, Hyderabad Campus
Second Semester 2023-2024
Tutorial-1 Solution
Course No CS F364 Course Title: Design and Analysis of Algorithm
Date:17/1/24
General Instructions: Argue logically. Write it in a manner that explains your logic very
clearly. Do not miss steps in between.
Q1 Prove the following function is Θ(n4 ). T (n) = 2n4 − 20n3 − 200n2 + 500n + 5000
Solution 1
T (n) = 2n4 − 20n3 − 200n2 + 500n + 5000 (1)
4
≤ 2n + 500n + 5000 (2)
≤ n4 (2 + 500/n3 + 5000/n4 ) (3)
4 3 4
≤ n (2 + 500/10 + 5000/10 ) for n ≥ 10 (4)
≤ n4 (2 + 0.5 + 0.5) (5)
4
≤ 3n for n ≥ 10 (6)
T (n) = 2n4 − 20n3 − 200n2 + 500n + 5000 (7)
4 3 2
≥ 2n − 20n − 200n (8)
4 2
≥ n (2 − 20/n − 200/n ) (9)
4 2
≥ n (2 − 20/100 − 200/100 ) for n ≥ 100 (10)
≥ n4 (2 − 0.2 − 0.02) (11)
4
≥ 1.78n for n ≥ 100 (12)
Thus for n ≥ 100, T (n) = O(n4 ) and T (n) = Ω(n4 ). Thus T (n) = Θ(n4 ).
Q2 Select the lowest Big-Oh complexity of each of these running time as given in table.
Running Time O(f (n))
500n + 5n1.5 + 50n log10 n O(n1.5 )
n2 log2 n + n(log2 n)2 O(n2 log n)
3 log8 n + log2 log2 log2 n O(log n)
n log3 n + n log2 n O(n log n)
2n + n0.5 + 0.5n1.25 O(n1.25 )
Q3 For each group of functions, sort the functions in increasing order of O complexity.
1. f1 (n) = n0.999999 log n, f2 (n) = 10000000n, f3 (n) = (1.000001)n , f4 (n) = n2
1000000 √
2. f1 (n) = 22 , f2 (n) = 2100000n , f3 (n) = n2 , f4 (n) = n n
√ n
n X
3. f1 (n) = n n , f (n) = 2n , f3 (n) = n10 2 2 , f4 (n) = (i + 1) [Midsem 2022-23]
2
i=1
1
Solution 3
1. The correct ordering is f1 (n), f2 (n), f4 (n), f3 (n). Note that log n < nc ∀c > 0. Thus f1 (n) =
n0.999999 log n = O(n0.999999 n0.000001 ) = O(n) = O(f2 (n)).
2. The correct ordering is f1 (n), f4 (n), f3 (n), f2 (n).
3. The correct ordering is f4 (n), f1 (n), f3 (n), f2 (n). 2 ), which is asymptotically
√ √ Of course, f√
4 (n) = Θ(n
√
n
smaller than n . We can write f1 (n) = n n log
= (2 2 )n n = 2 n log 2 n. Also, we can write
n 10 n n
10 log n +10log2 n
f3 (n) = n 2 = 2
2 2 2 =2
2 2 . The exponent of 2 in f1 (n) is a function which is slower
than linear function, whereas the exponent of 2 in f3 (n) grows linearly. Now between f3 (n) and
f2 (n), though exponents are of the same order but (20.5 )n is asymptotically smaller than 2n . Hence
f3 (n) = O(f2 (n)).
Q4 Let f (n) and g(n) be asymptotically positive function. Prove or disprove the following conjecture.
1. o(g(n)) ∩ ω(g(n)) = ∅. [Midsem 2021-22]
2. If f (n) = O(g(n)) then 2f (n) = O(2g(n) ). [Midsem 2021-22]
3. f (n) + g(n) = Θ(min(f (n), g(n))).
4. f (n) + g(n) = Θ(max(f (n), g(n))).
Solution 4
1. Let f (n) = o(g(n)) ∩ ω(g(n)). We know that for any c1 > 0, c2 > 0,
∃n1 > 0 such that 0 ≤ f (n) < c1 g(n) and
∃n2 > 0 such that 0 ≤ c2 g(n) < f (n)
If we pick n0 = max(n1 .n2 ), and let c1 = c2 , from the problem definition we get
c1 g(n) < f (n) < c1 g(n) which is not possible. Hence, o(g(n)) ∩ ω(g(n)) is empty.
2. Disprove: Let f (n) = 2n and g(n) = n. Clearly, f (n) = O(g(n)).
Consider 2f (n) = 22n = 4n ̸= O(2g(n) ).
3. This is not true. Let f (n) = n and g(n) = n2 . Then min(f (n), g(n)) = n. But f (n) + g(n) =
n + n2 ̸= Θ(n).
4. First note that f (n) + g(n) ≥ f (n) and f (n) + g(n) ≥ g(n). Thus f (n) + g(n) ≥ max(f (n), g(n)).
Therefore, f (n) + g(n) = Ω(max(f (n), g(n))).
Next, f (n) ≤ max(f (n), g(n)) and g(n) ≤ max(f (n), g(n)). Therefore, f (n)+g(n) ≤ 2(max(f (n), g(n))) =
O(max(f (n), g(n)). Hence f (n) + g(n) = Θ(max(f (n), g(n))).
