CSI2110 Tutorial
Analysis of Algorithms
Lucia Moura
Most exercises are taken from our textbook:
Goodrich, Tamassia and Goldwasser, Data structures and Algorithms in Java, 6 th edition
Exercises:
1) Determine the (worst-case) complexity of unique1 and unique2 using the
big-Oh notation; which algorithm is more efficient?
2) Determine the big-Oh of the pieces of code: example1, …, example5
(textbook exercises: R-4.9, R.10, R.11,R.12,R.13)
3) The number of operations executed by Algorithms A and B is 40n2 and 2n3,
respectively. Determine n0 such that A is better than B for all n>=n0.
4) Prove that if d(n) is O(f(n)) and e(n) is O(g(n)), then d(n)+e(n) is O(f(n)
+g(n)).
1.1) Big-Oh of unique1 ?
1.2 Big-Oh of unique2?
1) Determine the big-Oh of unique1 and unique2; which algorithm is
more efficient?
Example 1 and Example 2
Example 3 and Example 4
Example 5
3) The number of operations executed by
Algorithms A and B is 40n2 and 2n3,
respectively. Determine n0 such that A is
better than B for all n>=n0.
4) Prove that if d(n) is O(f(n)) and e(n) is O(g(n)),
then d(n)+e(n) is O(f(n)+g(n)).
Extras exercises:
• https://www.geeksforgeeks.org/algorithms-gq/analysis-of-algorithms-
gq/
• Suggested questions: Questions: 6, 8, 9, 10;
• Tricky challenge: Question 5
Appendix:
Big-Oh, Big-Omega, Big-Theta
Big-Oh (upper bound)
• given two functions f(n) and g(n), we say that
f(n) is O(g(n))
if and only if there are positive constants
c and n0 such that
f(n) c g(n) for all n n0
c • g(n)
f(n)
n0
n 13
big-Omega. (lower bound)
Definition: f(n) is (g(n)) (f(n) is big-Omega of g(n))
if there exist c > 0 and n0 1 such that
f(n) c • g(n) for all n n0
f(n)
c • g(n)
n0
n
Theorem: f(n) is (g(n)) iff g(n) is O(f(n))
14
big-Theta
Definition: f(n) is big-Theta of g(n)
f(n) is (g(n)) if there are constants c’ > 0 and c’’ > 0 and an
integer constant n0 1 such that
c’g(n) f(n) c’’g(n), for all n n0
Theorem.
f(n) is (g(n)) <===> if f(n) O(g(n)) AND g(n) O(f(n))
Theorem.
f(n) is (g(n)) <===> if f(n) O(g(n)) AND f(n) (g(n))
15
