Scribd
Upload
23 views1 page

Algorithm Analysis Problem Set 2018

This document contains 4 problems related to analyzing algorithms: 1) Order asymptotic functions from smallest to largest. 2) Give upper and lower bounds for recursive functions. 3) Use induction to solve a square root recurrence. 4) Prove a relationship between big-O and big-Omega notation.

Uploaded by

vidushi1121
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
23 views1 page

Algorithm Analysis Problem Set 2018

This document contains 4 problems related to analyzing algorithms: 1) Order asymptotic functions from smallest to largest. 2) Give upper and lower bounds for recursive functions. 3) Use induction to solve a square root recurrence. 4) Prove a relationship between big-O and big-Omega notation.

Uploaded by

vidushi1121
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Problem Set 1

Design and Analysis of Algorithms -2018

1. Order the following functions from asymptotically smallest to asymp-


totically largest (Indicate ties if any)

(a) f1 (n) = log n


(b) f2 (n) = log n3
(c) f3 (n) = log nlog n
(d) f4 (n) = n2.5
(e) f5 (n) = n2 log n
(f) f6 (n) = nlog n
(g) f7 (n) = log (n log n)
√
(h) f8 (n) = n
√
n
(i) f9 (n) = log log 2
(j) f10 (n) = n2


2. Give asymptotic upper and lower bounds for the following recurrences.
Assume T(n) is constant for sufficiently small n.
√
(a) T (n) = T ( n) + 1
(b) T (n) = f (n − 1) + 2n + 1
(c) T (n) = T (n − 1) + log n
(d) T (n) = 3T ( n2 ) + n log n
(e) T (n) = T (n − 1) + log n
(f) T (n) = 4T ( n2 + 5) + n2
√
3. Use mathematical induction to solve the recurrence T (n) = T ( n) + n

4. For any two positive functions f (n) and g(n), prove that f (n) =
O(g(n)) if and only if g(n) = Ω(f (n)).

You might also like