Chapter 3

Question 1

Show that for any real constants a and b, where b > 0,

Answer 1

Question 2

Is 2^{n + 1} = O(2^n)2n+1=O(2n)? Is 2^{2n} = O(2^n)22n=O(2n)?

Answer 2

Question 3

Prove that the running time of an algorithm is Θ(g(n)) if and only if its worst-case running time is O(g(n)) and its best-case running time is Ω(g(n)).

Answer 3

Question 4

Rank the following functions by order of growth; that is, find an arrangement 𝑔1, 𝑔2, … , 𝑔12 of the functions satisfying 𝑔1 = Ω(𝑔2 ), 𝑔2 = Ω(𝑔3 ), … , 𝑔11 = Ω(𝑔12). Partition your list into equivalence classes such that functions 𝑓(𝑛) and 𝑔(𝑛) are in the same class if and only if 𝑓(𝑛) = Θ(𝑔(𝑛)).

Answer 4

Question 5

Prove:

• 𝑛! = 𝑜(𝑛^𝑛).
• 𝑛! = ω(2 𝑛).
• lg(𝑛 !) = Θ(𝑛 lg 𝑛).

Answer 5

Answer

Question 6

.

Answer 6

f. Prove, from the first, we know that 0≤ f(n) ≤ cg(n) and we need to prove that 0 ≤ df(n )≤ g(n), which is straightforward with d=1/c.
g. Disprove, let’s pick f(n) = 2^nf(n)=2n. We will need to prove that

∃c1​,c2​,n0 ​: ∀ n ≥ n0​, 0 ≤ c1 ​⋅ 2^n/2 ≤ 2n ≤ c2 ​⋅ 2^n/2,

which is obviously untrue.

h. Prove, let g(n) = o(f(n)). Then

∃c,n0 ​: ∀ n≥n0​ , 0 ≤ g(n) < cf(n).

We need to prove that

∃c1​,c2​,n0 ​: ∀ n ≥ n0​ , 0 ≤ c1​f(n) ≤ f(n) + g(n) ≤ c2​f(n).

Thus, if we pickc1​=1 and c2​=c+1, it holds.

Question 7

Write a recursive algorithm to implement the Tower of Hanoi game. The Tower of Hanoi is a very famous game. In this game, there are three pegs and N number of disks placed one over the other in decreasing size. The objective of this game is to move the disks one by one from the first peg to the last peg. And there is only one condition, we cannot place a bigger disk on top of a smaller disk. What is the time complexity of your algorithm?

Answer 7