R-4.8 Order the following functions by asymptotic growth rate. 4nlogn+2n 2^10 2^

Question

R-4.8 Order the following functions by asymptotic growth rate.

4nlogn+2n 2^10 2^logn

3n+100logn 4n 2^n

n^2 +10n n^3 nlogn

R-4.9 Give a big-Oh characterization, in terms of n, of the running time of the example1 method shown in Code Fragment 4.12.

R-4.10 Give a big-Oh characterization, in terms of n, of the running time of the example2 method shown in Code Fragment 4.12.

R-4.11 Give a big-Oh characterization, in terms of n, of the running time of the example3 method shown in Code Fragment 4.12.

R-4.12 Give a big-Oh characterization, in terms of n, of the running time of the example4 method shown in Code Fragment 4.12.

R-4.13 Give a big-Oh characterization, in terms of n, of the running time of the example5 method shown in Code Fragment 4.12.

Explanation / Answer

We know that asymptotic Growth Rate follows this Order :

Constant <<Logarithmic <<< Polynomial <<Exponential

2^10 , 2^logn , 3n+100logn , 4n , nlogn , 4nlogn+2n , n^2 +10n , n^3 , 2^n

2^logn is n

R-4.9 Give a big-Oh characterization, in terms of n, of the running time of the example1 method shown in Code Fragment 4.12.
Answer : O(n)
Explanation: We can see that the for loop run n time , So maximum times tne loop will run is n, SO its O(n)

R-4.10 Give a big-Oh characterization, in terms of n, of the running time of the example2 method shown in Code Fragment 4.12.
Answer : O(n)
Explanation: We can see that the for loop run n/2 time , So maximum times tne loop will run is n/2, So its O(n/2) which is nothing but O(n) we need to ignore constants

R-4.11 Give a big-Oh characterization, in terms of n, of the running time of the example3 method shown in Code Fragment 4.12.
Answer : O(n2)
Explanation: We can see that when j = 0, loop runs 1 time. when j is 1 loop runs 2 times , that means
Loop runs for 1 + 2 + 3+ 4 + 5+ 6 ...n
=> n*(n+1)/2
=> O(n2)

R-4.12 Give a big-Oh characterization, in terms of n, of the running time of the example4 method shown in Code Fragment 4.12.
Answer : O(n)
Explanation: We can see that the for loop run n time , So maximum times tne loop will run is n, SO its O(n)

R-4.13 Give a big-Oh characterization, in terms of n, of the running time of the example5 method shown in Code Fragment 4.12.
Answer : O(n3)
Explanation: We can see that the first for loop run n time , Second runs n2 TIME BECAUSE The first runs n and 2nd runs itself as n so n2 , Third runs n3 time BECAUSE The second runs n2 and 3nd runs itself as n so n3 ,


Thanks, let me know if you have any concerns/doubts

PLEASE RATE, THANKS

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

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