BIG OH ranking, Transitivity, and Code Snipet Runtime Rank the following nine fu

Question

BIG OH ranking, Transitivity, and Code Snipet Runtime

Rank the following nine functions by order of growth, i.e., find an arrangement f_1, f_2, of the functions satisfying f_1 element O (f_2), f_2 element O (f_3), Partition your list into equivalence classes such that f and g are in the same class if and only if f element theta (g). For every two functions f_i, f_j that are adjacent in your ordering, prove shortly why f_i element O (f_j) holds. And if f and g are in the same class, prove that f element theta (g). 4^n, 3^n, 2_squareroot n, 2n^3 + 4, 1, log n, log log n, 3_squareroot n, 2_squareroot n^6 Bear in mind that in some cases it might be useful to show f (n) element o (g (n)), since o (g (n)) Subset O (g (n)). If you try to show that f (n) element o (g (n)), then it might be useful to apply the rule of 1'Hopital which states that lim_x rightarrow infinity f (n)/g (n) = lim_x rightarrow infinity f' (n)/g' (n) if the limits exist: where f' and g' are the derivatives of f and g, respectively. Use the definition of big-Oh to prove: If f (n) element O (g (n)) and g (n) element O (h (n)) then f (n) element O (h (n)) Give the theta-runtime for the code snippet below, depending on n. Justify your answer. for (i =n * n: i > = 1: i = i - 4) for (j = n * n: j > = 1: j = j/4) print (" ");

Explanation / Answer

1) Ranking them In Ascending Order

1 , loglogn , log n , n1/3 , n1/2 , n3 , , 2n3 + 4 , 3n , 4n

Idea is exponential >>>> Polynomial >>> Logarithmic

2) Transitivity
If f(n) O(g(n)), that means c*g(n) >= f(n)

AND
If g(n) O(h(n)), that means c*h(n) >= g(n)

The means c1*h(n) >= c2* g(n) >= f(n)

So we can easily write f(n) O(h(n)) by definition and we know that c1*h(n) >= f(n)

hence Proved

3) Code Snippets

Outer loop will run for n2 / 4 times , lets see How
Lets say we dont know how many times loop will run , lets take it as K. We can see that
Everytime n2 is decremented by 4 that means n2 - 4K = 0
=> K = n2 / 4 for Outer Loop

For Inner loop will run for Log4 n lets see How
Lets say we dont know how many times loop will run , lets take it as K. We can see that
Everytime n2 is decremented by 4 that means n2 - 4k = 0
=>   n2 = 4k , Take log both the sides we get K = 2Log4 n for Inner Loop

So, the Total Time Complexity is O(n2 log4 n)

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.