Data structure and algorithms lab 2

1. Order the following functions from slowest growing to fastest growing by inspecting their graphs.
a. T(n) = n
b. T(n) = 1
c. T(n) = sqrt(n)
d. T(n) = n2
e. T(n) = log n

Answer

The order is from the slowest growing to fastest growing
a. T (n) = 1

b. T (n) = log n

c. T (n) = √n

d. .T (n) = n

e. T (n) = n^2

2. Give the big O for the following functions by determining the dominant term.
a. T(n) = 2n2 + 3n – 7

Answer
The dominant term is 2n^2
T(n) = 2n^2 + 3n – 7 is big O (n^2)

b. T(n) = 2n3/n + n2- 3n*n + 12 [Careful. Tricky.]

Answer
the dominant term is 3n*n
T(n) = 2n^3/n + n^2- 3n*n + 12 is big O (1)

c. T(n) = log(n) + n1/2

Answer
the dominant term is n^(1/2)
T(n) = log(n) + n^(1/2)is big O (√n)

d. T(n) = 2nlog(n) + n2 + 100n + 1000

Answer
the dominant term is n^2
T(n) = 2n log(n) + n^2+ 100n + 1000 is big O (n^2)

e. T(n) = n0 + 27/6

Answer
the dominant term is 27/6
T(n) = n^0 + 27/6 is big O (1)

3. Prove using the definition of Big O that
a. T(n) = 2n2 + 3n + 1 is O(n2)

Answer
T(n)=2n^2 + 3n + 1 and let g(n)= n^2
T(n) ≤ C.g(n)
whenever n> k
Since when n> 1, n< n^2 and 1< n^2 0 ≤ 2n^2+ 3n + 1 ≤ 2n^2+ 3n^2+ n^2= 6n^2 We can take C = 6 and k = 1 as witnesses to show that T(n) is O(n^2)

b. T(n) = 2n2 + 3n + 1 is O(n3)

Answer
T (n) =2n^2 + 3n + 1 and let g (n) = n^3 T (n) ≤ C.g(n) Whenever n> k
Since when n> 1, n< n^3 and 1< n^3 0 ≤ 2n^2+ 3n + 1 ≤ n^3 We can take C = 1 and k = 4 as witnesses to show that T (n) is O (n^3)

c. T(n) = 2n2 + 3n + 1 is not O(n)

Answer
Suppose there are constants C and k for which 2n^2 + 3n + 1 ≤ Cn, whenever n> k
Then (by dividing both sides of 2n^2+ 3n + 1 ≤ Cn) by n, then 2n + 3 + 1/n ≤ C must hold for all n> k
A contradiction

d. T(n) = log(n) is O(log(n))

Answer
T (n) =log (n) and let g (n) =log (n)
T (n) ≤ C .g(n)
Whenever n> k
0 ≤ log (n) ≤ log (n)
We can take C = 1 and k = 2 as witnesses to show that T (n) is O (≤ log (n))

e. T(n) = log(n) is O(n)

Answer
T (n) = log (n) and let g (n) = n
T (n) ≤ C. g (n)
Whenever n> k
Since when n> 2, log (n) < n 0 ≤ log (n) ≤ n We can take C = 1 and k = 2 as witnesses to show that T (n) is O (n)

4. Prove using the definition of Big Ω that

a. T(n) = 2n2 + 3n + 1 is Ω (n2)

Answer
T (n) is Ω (g (n)) where g (n) = n^2 When C=1 and k=1 T (n) ≥ C. g (n) when n> 1
Then
T (n) = 2n^2 + 3n + 1 ≥ n^2
For all positive real numbers n

b. T(n) = 2n2 + 3n + 1 is not Ω (n3)

Answer
Suppose there are constants C and k for which 2n^2 + 3n + 1 ≥ Cn, whenever n> k
Then (by dividing both sides of 2n^2+ 3n + 1 ≥Cn) by n, then 2n + 3 + 1/n ≥ C must hold for all n> k
A contradiction

c. T(n) = 2n2 + 3n + 1 is Ω (n)

Answer
T (n) is Ω (g (n)) where g(n)=n
When C=1 and k=1 T (n) ≥ C. g (n) when n> 1
Then
T (n) = 2n^2+ 3n + 1 ≥ n
For all positive real numbers n

d. T(n) = log(n) is Ω (log(n))

Answer
T(n) is Ω(g(n)) where g(n)= log(n)
when C=1 and k=1 T(n) ≥ C.g(n) when n> 1
then
T(n) = log(n) ≥ log(n)
for all positive real numbers n>1

e. T(n) = log(n) is Ω (1)

Answer
T (n) is Ω (g (n)) where g (n)=1
When C=1 and k=2 T (n) ≥ C. g(n) when n> 2
Then
T (n) = log (n) ≥ 1
For all positive real numbers n>2

5. Prove using the definition of Big Θ that [Hint: Refer to the relevant parts of 3 and 4.]
a. T(n) = 2n2 + 3n + 1 is Θ (n2)

Answer
2n^2 + 3n + 1 ≤ 6n^2 for n> 1, since 0≤2n^2 + 3n + 1 ≤ 6n^2
Hence,2n^2 + 3n + 1 is O(n^2)
n2 is clearly Ω(2n^2 + 3n + 1 )
Hence, 2n^2 + 3n + 1 is ϴ(n^2)

b. T(n) = log(n) is Θ (log(n))

Answer
log(n)≤ log(n) for n> 1, since 0≤log(n)≤ log(n)
Hence, log(n) is O(log(n))
log(n) is clearly Ω(log(n) )
Hence, log(n) isϴ(log(n))

6. [Bonus: 1 extra mark which can be carried forward to another lab.]
[You are not responsible for this material on the exams. This is for top students who want to know more.]
View the presentation on L’Hopital’s Rule at https://www.youtube.com/watch?v=6IjVGfbhe9w and then use L’Hopital’s Rule to show T(n) = 3n2 + 2n + 1 is O(n2) by showing 4n2 grows faster than = 3n2 + 2n + 1.

Answer
L’Hospital Rule
Let us assume
T (n) >0
g (n)>0
Where T (n) =3n^2 +2n+1
g (n)=4n^2
lim┬(n→∞)⁡〖((3n^2+2n+1)/(4n^2 ))^ 〗= ∞/ ∞
Using L’Hospital lim┬(n→∞)⁡〖((3n^2+2n+1)/(4n^2 ))^ 〗=lim┬(n→∞)⁡〖((6n+2)/8n)^ 〗= ∞/ ∞
Using L’Hospital lim┬(n→∞)⁡〖((6n+2)/8n)^ 〗=lim┬(n→∞)⁡〖(6/8)^ 〗= 3/ 4
Therefore 4n^2 is going to infinity faster in 4/ 3 times as quickly as 3n^2 +2n+1