Asymptotic Notations

and Recurrences Practice Set 1 Lecturer: Varun Rajan

1. The following list of functions lists the exact number of steps required by a variety of
algorithms, in the best case and in the worst case, respectively. For each of them, give tight
upper and lower bounds in terms of the Big-O and Big-Ω notations, respectively. If these
bounds match, then specify the bound using the Θ notation.
Note that a tight upper (resp. lower) bound on a function f (n) is a function g(n) such that
f (n) = O ( g(n)) (resp. f (n) = Ω( g(n))) and f (n) 6= o ( g(n)) (resp. f (n) 6= ω ( g(n)))

1. 2n2 + n log n and 5n3 + 2n − 1132

2. 10 · 3n + 6n log n and 3 · 2n + 100 · 3n + 29n log n
√
3. 79n + 11n log n and 4n n + 9n(log n)4
2 3
4. 42 and 16nlog n + 2n2log n

2. In each of the following questions, the functions f (n), g(n), for n ∈ Z+ , contain arbitrary
constants a, b, c and d. For each pair, determine if f (n) = O ( g(n)) irrespective of the
value of the constants. If not, specify the conditions to be imposed on the constants under
which f (n) = O ( g(n)). Assume that the logarithms are given in base 2, unless specified
otherwise.
For example, if f (n) = anc and g(n) = bnd , then f (n) = O ( g(n)) if and only if c ≤ d
(Why?).

1. f (n) = a logc n and g(n) = b logd n

2. f (n) = a(logc n)2 and g(n) = b logd n
3. f (n) = an logc n and g(n) = bn1+e , where e > 0 is a small constant
4. f (n) = 3logc n and g(n) = 2logd n
5. f (n) = 3an and g(n) = 2bn
6. f (n) = 3a logc n and g(n) = 2b logd n
2
7. f (n) = (log n)log n and g(n) = 2(logd n)
8. f (n) = nc and g(n) = (log n)b logd n
9. f (n) = a logc n and g(n) = b log∗ n
∗
10. f (n) = n and g(n) = (log n)log n

3. For each of the following questions, determine if it is always true, always false or neither.

1. f = O ( g) and g = O ( f ) 7. a f (n) = O ( f (n)); a constant

2. f = O ( g) and g = Ω( f ) 8. f (n) = O f (n)2
3. f = O ( g) and g = o ( f ) 9. f = O ( g) and 2 f (n) = O 2g(n)
4. f 6= O ( g) and g 6= O ( f )
10. f = o ( g) and log f (n) = O (log g(n))
5. f = Ω( g) and g = Ω( f )
11. f (n) + g(n) = Θ(max ( f (n), g(n)))
6. c = Θ (1)
12. f (n) + O ( f (n)) = Θ( f (n))

If your answer is neither always true nor always false, then give an example to show when
it is true and an example for when it is false. If possible, also make minor modifications to
the statement to make it either always true or always false.
n
4. Show that ∑ i k
= O n k +1
.
i =1

5. Show that if f (n) = O (h(n)) and g(n) = O (h(n)) then f (n) g(n) = O h(n)2 .

6. For each of the following recurrences, solve it to give both an upper bound and a lower
bound on T (n); using the recursion tree method would generally be easier, though not
required. You may also try to solve these using the Master method.

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

2. T (n) = T (2n/3) + Θ(n)
3. T (n) = 2T (n/2) + Θ(1)
4. T (n) = 3T (n/3) + Θ(n)
5. T (n) = 4T (n/2) + Θ(1)
6. T (n) = 4T (n/2) + Θ(n2 )
7. T (n) = T (n − 2) + Θ(1)
8. T (n) = T (n − 1) + Θ(n2 )
9. T (n) = 2T (n − 1) + Θ(1)
10. T (n) = T (n/3) + T (2n/3) + Θ(n)
11. T (n) = T (n/2) + T (n/4) + Θ(1)
12. T (n) = T (n/2 + log n) + Θ(n)
Hint: Use the fact that n/2 < n/2 + log n < 3n/4 and that T (n) is monotonically
increasing
√
13. T (n) = T ( n) + Θ(n)
√ √
14. T (n) = nT ( n) + Θ(n)
T (n)
Hint: Divide the equation by n and let S(n) = n .
n
15. T (n) = 2T (n/2) + log n
16. T (n) = 2T (n − 2) + 1
17. T (n) = 3T (n − 2) + n

7. Solve each of the following recurrences using the characteristic root method and express
the solution using the Big-O notation.

1. T (n) = T (n − 1) + T (n − 2)
2. T (n) = 5T (n − 1) − 6T (n − 2)
3. T (n) = 3T (n − 1) − 2T (n − 2)
4. T (n) = 4T (n − 1) − T (n − 2) − 6T (n − 3)
5. T (n) = T (n − 1) + T (n − 2) + c
Hint: Why can’t you directly apply the characteristic root method here? Think in
terms of the recursion tree and how the term c relates to it.

Page 2
8. For each of the following algorithms, compute the best upper and lower bounds you can.
You may ignore the correctness or the purpose of the algorithms.
(a) C OMBINE ( A[1..n], B[1..m])
Input. Arrays A, B
Output. Array C in sorted order, containing all elements from A, B
1: j = 1, k = 1
2: for i = 1 to n + m do
3: if A[ j] ≤ B[k ] then
4: C [i ] = A [ j ]
5: j = j+1
6: else
7: C [i ] = B [ k ]
8: k = k+1
9: end if
10: end for
11: return C
(b) IS P RIME (n )
Input. Integer n ≥ 4
Output. YES if n is a prime number, NO otherwise.
1: j = 1, k = 1 √
2: for i = 2 to n + 1 do
3: if n mod i == 0 then
4: return NO
5: end if
6: end for
7: return YES
(c) ULTI S EARCH ( A [1..n ], x )
Input. An unsorted array A of integers, an integer x
Output. YES if x is an element of A, NO otherwise.
1: mid = 1+2 n
2: if ultiSearch( A[1..mid − 1], x ) == YES then
3: return ultiSearch( A[1..mid − 1], x )
4: else if ultiSearch( A[mid + 1..n], x ) == YES then
5: return ultiSearch( A[mid + 1..n], x )
6: else if A[mid] == x then
7: return YES
8: end if
9: return ultiSearch( A[1..mid − 1], x )
(d) WEIRD S EARCH ( A [1..n ], x )
Input. An unsorted array A of integers, an integer x
Output. YES if x is an element of A, NO otherwise.
1: mid = 1+2 n
2: if A[mid] == x then
3: return YES
4: else if weirdSearch( A[1..mid − 1], x ) == YES or
5: weirdSearch( A[mid + 1..n], x ) == YES then
6: return YES
7: end if
8: return NO

Page 3
(e) F (n)
Input. Integer n ≥ 0
Output. The value of F (n), where F is defined as F (i ) = F (i − 1) + i − 1 if i is odd,
F (i ) = F (i − 1) + F (i − 2) if i is even and F (0) = 0.
1: if n == 0 then
2: return 0
3: else if n mod 2 == 1 then
4: return F (n − 1) + n − 1
5: end if
6: return F (n − 1) + F (n − 2)
(f) F (n)
Input. Integer n ≥ 0
Output. The value of F (n), where F is defined as F (i ) = F (i − 1) + 2F (i − 2) if i is
odd, F (i ) = 2F (i − 1) + F (i − 2) if i is even and F (0) = F (1) = 0.
1: if n == 0 or n == 1 then
2: return 0
3: else if n mod 2 == 1 then
4: return F (n − 1) + 2(n − 2)
5: end if
6: return 2F (n − 1) + (n − 2)

Page 4