Question

1 question) Arrange the following in the order of their growth rates, from least to greatest: (5 pts)

n³                     n²         nⁿ        lg n     n!       n lg n              2ⁿ                     n

2 question)Show that 3n³ + n² is big-Oh of n³. You can use either the definition of big-Oh (formal) or the limit approach. Show your work! (5 pts.)

3 question)Show that 6n² + 20n is big-Oh of n³, but not big-Omega of n³. You can use either the definition of big-Omega (formal) or the limit approach. Show your work! (10 pts.)

4 question)Show that n³ is big-Omega of n². You can use either the definition of big-Omega (formal) or the limit approach. Show your work! (5 pts.)

5 question) Consider the following algorithm:

            int j = 1;

            int k = 1;

            for (i = 1; i <= 10; i++)

                        j = j * 100;      

            for (i = 1; i <= 20; i++)

                        k = k * 2;          

            What is the running time, T(n)? Give both the exact function T(n), and then give a big-    Theta estimate of T(n). Show your work. For example, if T(n) is exactly n² + 3n, then T(n) is big-Theta of n². Show your work! (10 pts.)

6 question)Consider the following algorithm:

            int k = 0;

            for (i = 2; i <= n; i++)

                        for (j = 0; j <= n; j++)

                                    k = i + j;    

            What is the running time, T(n)? Give both the exact function T(n), and then give a big-    Theta estimate of T(n). Show your work! (10 pts.)

7 question)

If the worst case time of algorithm A is big-oh of that of B, then B is not faster than A for large problems. (True or False) Explain! Then consider if A is strictly big-oh, how about then? (5 pts.)

8 question)n⁴ is big-oh of n^6. (True or False) Explain! (5 pts.)

9 question)Since 2(2n + 5) >= 3n for n >= 0, and 3n >= 2n + 5 for n >= 5, 2n + 5 is big-oh of 3n. (True or False) Explain or show work! (5 pts.)

10 question) If f(n) is big-theta of g(n), then the value of f may be infinitely away from that of g. (True or False) Explain! (5 pts.)

Answer 1

HI, I have answered first two questions.

Please repost others in separate post.

1)

logn < n < nlogn < n^2 < n^3 < 2^n < n! < n^n

2)
Given
3n^3 + n^2 = O(n^3)

Proff:
   3n^3 + n^2 <= 3n^3 + n^3

   3n^3 + n^2 <= 4n^3

   So, 3n^3 + n^2 = O(n^3), c = 4, n0 = 1