CS-510 Design & Analysis of Algorithms LUMS

Solution: Asymptotic Analysis

Problem 1. Show that 2n+1 is O(2n )

Solution: We have 2n+1 = 2 · 2n , hence by definition of the set O(2n ), 2n+1 ∈ O(2n ),
here n0 = 1 and c = 2.

Problem 2. In each case below, demonstrate whether the given expression is true or
false.

a) 5n3 ∈ O(n3 )
Solution: True, by definition. Take c = 5 and n0 = 1.

b) 100n2 ∈ O(n4 )
Solution: True by definition. Take c = 10 and n0 = 1 or c = 1, and n0 = 10.

c) log n2 ∈ O(log n)
Solution: True, By definition of log, log n2 = 2 log n, hence taking c = 2 and n0 = 1,
we get log n2 ≤ c log n.

d) (n2 + 7n − 10)3 ∈ O(n6 )

Solution: True, (n2 + 7n − 10)3 ≤ (n2 + 7n)3 ≤ 73 (n2 + n)3 ≤ 73 (n6 + 10n5 ) ≤
73 · 11 · n6 , hence taking c ≥ 73 · 11 and n0 = 1, by definition of O(n6 ), the function
(n2 + 7n − 10)3 ∈ O(n6 )
√
e) n ∈ O((log n)3 )
√
Solution: False. Suppose √n ∈ O((log n)3 ), by definition it means there exists
constants c and n√ 0 such that n ≤ c(log n)3 for n ≥ n0 . Simplifying this inequality it
3
gives us that c ≥ n/(log n) , which means c is not a constant it must be bigger than
an increasing function of n. As n grows c must grow too, hence it is not a constant.

Problem 3. In each row of the following table, write whether f = O(g), or f = Ω(g),
or both i.e. f = Θ(g)

Solution:

Asymptotic Analysis 1
CS-510 Design & Analysis of Algorithms LUMS
f (n) g(n) Your Answer

100 17 f = Θ(g)
10200 n − 10200 f = O(g)
n2 log 300 n log n f = Ω(g)
n100 2n f = O(g)
n log n n − 100 f = Ω(g)
√
n log n f = Ω(g)
n1.01 n + 100 f = Ω(g)
2 log n log(n2 ) f = Θ(g)
log(n2 ) (log n)2 f = O(g)

Problem 4. Order the following functions of n from the smallest to largest complexity.
If two have the same complexity put them in one line next to each other.

n log n, (n − 5)(n), 10 log 300, n + 7 log(n2 ),

3n8
2n , 10n2 + 15n, 17, 15n3 + n log n,
n6
10200 , n2 log 300, 2 log10 10200 , n2 + 7 log(n2 ),
2 √
3n , n2 + n, n2 log n, n4 + n2 + n2 log n, n4

Solution:
10 log 300, 17, 10200 , 2 log10 10200

n + 7 log(n2 )

n log n
√
(n − 5)(n), 10n2 + 15n, 3n8 /n6 , n2 log 300, n2 + 7 log(n2 ), n2 + n

n2 log n

15n3 + n log n,

n4 + n2 + n2 log n, n4

2n
2
3n

Asymptotic Analysis 2
CS-510 Design & Analysis of Algorithms LUMS
Problem 5. [Complexity Classes]
• Order the following functions of n from the smallest to largest complexity and also
identify the complexity class for each. If two have the same complexity put them
in one line next to each other.
10200 , n2 log 300, 2 log10 10200 , n2 + 7 log(n2 ),
2 √
3n , n2 + n, n2 log n, n4 + n2 + n2 log n, n4

• Briefly explain next to each line why these functions are in the same complexity
class.

Solution:
10200 , 2 log10 10200 , constant
√
n2 log 300, n2 + 7 log(n2 ), n2 + n Θ(n2 )

n2 log n, Θ(n2 log n)

n4 + n2 + n2 log n, n4 Θ(n4 )
2 2
3n Θ(3n )

Problem 6. Let f (n) and g(n) by asymptotically positive functions. Prove or disprove
each of the following conjectures.
1. f (n) = O(g(n)) implies g(n) = O(f (n)).
Solution: Disprove, n = O(n2 ), but n2 6= O(n).
2. f (n) + g(n) = Θ(min(f (n), g(n))).
Solution: Disprove, n2 + n 6= Θ(min(n2 , n)) = Θ(n).
3. f (n) = O(g(n)) implies lg(f (n)) = O(lg(g(n))), where lg(g(n)) ≥ 1 and f (n) ≥ 1
for all sufficiently large n.
Solution: Prove, because f (n) ≥ 1 after a certain n ≥ n0 .

∃c, n0 : ∀n ≥ n0 , 0 ≤ f (n) ≤ cg(n)

⇒ 0 ≤ lg f (n) ≤ lg(cg(n)) = lg c + lg g(n).

4. f (n) = O(g(n)) implies 2f (n) = O(2g(n) ).

Solution: Disprove, because 2n = O(n), but 22n = 4n 6= O(2n ).
5. f (n) = O((f (n))2 ).
Solution: Prove, 0 ≤ f (n) ≤ cf 2 (n) is trivial when f (n) ≥ 1, but if f (n) < 1 for
all n, it’s not correct. However, we don’t care this case.
6. f (n) = O(g(n)) implies g(n) = Ω(f (n)).
Solution: 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.

Asymptotic Analysis 3
CS-510 Design & Analysis of Algorithms LUMS
7. f (n) = Θ(f (n/2)).
Solution: Disprove, let’s pick f (n) = 2n . We will need to prove that

∃c1 , c2 , n0 : ∀n ≥ n0 , 0 ≤ c1 · 2n/2 ≤ 2n ≤ c2 · 2n/2 ,

which is obviously untrue.

8. f (n) + o(f (n)) = Θ(f (n)).

Solution: 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 pick c1 = 1 and c2 = c + 1, it holds.

Problem 7. Prove or disprove: it is asymptotically faster to square an n-bit integer than

to multiply two n-bit integers.

Solution: False, squaring an n-bit integer and multiplying two n-bit integers have
the same asymptotic complexity.
Proof: It is known that (a + b)2 = a2 + b2 + 2ab and (a − b)2 = a2 + b2 − 2ab.
2 2
Subtracting the two equations: (a + b)2 − (a − b)2 = 4ab. Thus, ab = (a+b) −(a−b)
4
This shows that multiplication of any two integers a and b can be done by performing
the following operations: 1 addition, 2 subtractions, 1 division and 2 squares. Therefore,
the complexity of multiplying two numbers is a constant number of additional opera-
tions more than a constant factor of the complexity of a square operation and thus is
asymptotically same as the complexity of squaring.

Asymptotic Analysis 4