Have a question?
Message sent Close

CS330 Duke University Hw1-solutions

Sandra Watson
0 reviews
  • Description
  • Full Document

Hw1-solutions – CS330 Duke University

Duke University

Design and Analysis of Algorithms (COMPSCI 330)

COMPSCI 330, Design and Analysis of Algorithm
Homework 1 Solutions
Problem 1
Part (a)
There are many examples that will work. Consider defining each function as follows:
f1(n) = 2n, f2(n) = n+1, g1(n) = g2(n) = n.
Clearly, f1(n) = Θ(f2(n)) since 2n ≤ 2(n + 1) and n + 1 ≤ 2n for all n ≥ 1. It’s also clear that g1(n) =
Θ(g2(n)) since g1(n) = g2(n).
However, f1(n)−g1(n) 6= O(f2(n)−g2(n)). Namely, for any constant c > 0, we have that f1(n)−g1(n) =
n > c = c ·(f2(n) − g2(n)) for all n > c. In other words, no matter what constant we choose to scale
f2(n)−g2(n) by, f1(n)−g1(n) will always dominate after a certain point (implying there does not exist a
valid c and n0 pair satisfying the definition of O(·)). Therefore, f1(n)−g1(n) 6= Θ(f2(n)−g2(n)).



CS330 Duke University Hw1-solutions

NOTE: Please check the details before purchasing the document.