1Order the following functions by growth rate : N, N12, N1.5, N2, NlogN, N(logN)

Question

1Order the following functions by growth rate : N, N12, N1.5, N2, NlogN, N(logN)2, NlogN22N 2N, 2N2, 37, N3, and N2logN. Also, Indicate which functions grow at the same rate. 2) Describe the order of magnitude of each of the following code sections, using Big-O notation a) static int Square_Root int num) int i-num while(i * i>-num) { b) From Text book 48 (e) count 0; forti-i; i. N; i++) count count+t c) From Texthook 48 (e) value N; count = 0; while (value > I value = value/2; count++ Consider four programs-A, B, C, and D-that have the following performances: A- O(logrn) B-O(n) 3) D-0(2n If each program requires 10 seconds to solve a problem of size 1000, estimate the time required by each program for a problem of size 2000.

Explanation / Answer

1. Increasing order of growth rate: 37, 2/N, N1/2, N, 2N, NlogN, NlogN2, N(logN)2, N1.5, N2, N2logN, N3, 2N/2

N and 2N grow at the same rate.

Similary, NlogN and NlogN2 grow at the same rate.

2. a) O(sqrt(num))

b) O(N)

c) O(N)

3. a) Given that O(log n) takes 10 seconds to solve a problem of size 1000.

=> c*log(1000) = 10

=> c*log(2000) = c*log(2) * log(1000) = log(2) * 10

b)

Given that O(n) takes 10 seconds to solve a problem of size 1000.

=> c* 1000 = 10

=> c*2000 = c*2 * 1000 = 20

c)

Given that O(n^2) takes 10 seconds to solve a problem of size 1000.

=> c* (1000^2) = 10

=> c*(2000^2) = c*4 * 1000 = 40

d)

Given that O(2n) takes 10 seconds to solve a problem of size 1000.

=> c* (21000) = 10

=> c*(22000) = c*21000*21000 = 100

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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