Description
1)
For each of the following statements, specify whether it is true or not. Explain your
reasoning for each of them.
a) log2 𝑛
2 + 1 ∈ Ο(𝑛)
b) √𝑛(𝑛 + 1) 𝜖 Ω(𝑛)
c) 𝑛
𝑛−1
𝜖 𝜃(𝑛
𝑛)
d) 𝑂(2
𝑛 + 𝑛
3
) ⊂ 𝑂(4
𝑛
)
e) 𝑶(2 log3 √𝑛
3
) ⊂ 𝑂(3 log2 𝑛
2
)
f) log2 √𝑛 and (log2 𝑛)
2
are of the same asymptotical order.
2) Order the following functions by growth rate and explain your reasoning for each of them.
𝑛
2
, 𝑛
3
, 𝑛
2
log 𝑛, √𝑛, log 𝑛, 10𝑛
, 2
𝑛
, 8
log𝑛
3) What is the time complexity of the following programs? Explain by giving details.
a)
void f( int my_array[]){
for(int i=0;i