Question

In: Computer Science

Match the following functions to their respective big-O notation 1. 5 + 0.001n3 + 0.025n 2....

Match the following functions to their respective big-O notation

1. 5 + 0.001n3 + 0.025n

2. 100nlog n + n5 + 100n

3. n2log n + nlog n

4. 2n + n5 + 5n

5. 100n + 0.01n2

A.

O(n3)

B.

O(5n)

C.

O(n2)

D.

O(n5)

E.

O(n2log n)

Solutions

Expert Solution

Ans ). Here's the matching.

1). 5 + 0.001n3 + 0.025n = A). O(n3)  Since we can clearly see that the highest power is 3 and c*n3 will be an upper bound of the given polynomial for the appropriate choice of c.

2).  100nlog n + n5 + 100n = D). O(n5) Here also the largest or we can say the fastest growing term is n5, all the other terms say nlogn are smaller that this because we know logn is smaller than n. and therefore nlogn is smaller that n*n which is obviously smaller that n5.

3).  n2log n + nlog n = E). O(n2log n) We can clearly see that larger term of the given function is n2log n.

4). 2n + n5 + 5n = B).   O(5n) As we can see that we have an exponential term here and all the other terms are polynomial terms. Therefore here also 5n is clearly the major term.

5).  100n + 0.01n2  = C). O(n2)   Here also we can see that n2 term is the largest among all the terms of the given function.

Hope it helps. Feel free to ask any doubts in commnets, I'll be more than happy to answer any of them. Don't forget to upvote if it helped :).


Related Solutions

Big-O: Describe the worst case running time of the following pseudocode or functions in Big-Oh notation...
Big-O: Describe the worst case running time of the following pseudocode or functions in Big-Oh notation in terms of the variable n. Show your work a) O( ) int m1(int n, int m) { if (n < 10) return n; else if (n < 100) return happy (n - 2, m); else return happy (n/2, m); } ----------------------------- b) O ( ) void m2 (int n) { j = 0; while (j < n) { for (int i = 0;...
1. Find the big−O, big−Ω estimate for x7y3+x5y5+x3y7. [Hint: Big-O, big- Θ, and big-Omega notation can...
1. Find the big−O, big−Ω estimate for x7y3+x5y5+x3y7. [Hint: Big-O, big- Θ, and big-Omega notation can be extended to functions in more than one variable. For example, the statement f(x, y) is O(g(x, y)) means that there exist constants C, k1, and k2 such that|f(x, y)|≤C|g(x, y)|whenever x > k1 and y > k2] 2. Find a div b and a mod b when: (a) a = 30303, b = 333 (b) a = −765432, b = 3827 3. Convert...
42. Describe the order of growth of each of the following functions using O notation. a....
42. Describe the order of growth of each of the following functions using O notation. a. N2+3N b. 3N2+N c. N5+100N3+245 d. 3NlogN+N2 2 e. 1+N+N2 +N3 +N4 f. (N * (N − 1)) / 2 Describe the order of growth of each of the following code sections, using O notation: count = 0; for (i = 1; i <= N; i++) count++; count=0; for (i = 1; i <= N; i++) for (j = 1; j <= N; j++)...
I have a function and I was tild to give the big o notation of it...
I have a function and I was tild to give the big o notation of it Analyze the worst-case run-time complexity of the member function reverse() of the List. Give the complexity in the form of Big-O. Your analysis can be informal; however, it must be clearly understandable template <typename T> void List<T>::reverse() { auto current = head; // starting from head node   while(current != nullptr) // till current node is not last (next after last)   {     std::swap(current->next, current->prev); //...
How to determine whether the following statements about big-O notation are true or false? (a) Let...
How to determine whether the following statements about big-O notation are true or false? (a) Let f(n) = √ n log n − 4, then f(n) = O(n^ 2) (b) Let f(n) = 4 n + 2 log^ 2 (n), then f(n) = O(log^ 2 (n)) (c) Let f(n) = 5 √ n + 2, then f(n) = Ω(log^ 4 (n)) (d) Let f(n) = 5 n^ 2 + 5 n log n + 4, then f(n) = O(n^3 )...
1. State and explain the definition of big-O. 2. Explain why we use big-O to compare...
1. State and explain the definition of big-O. 2. Explain why we use big-O to compare algorithms. 3. Explain why binary search runs in O(log n) time. 4. Under what conditions is it possible to sort a list in less than O(nlog n) time? 5. List and explain the worst-case and average-case running times for each Vector method below: (a) insert(iterator here, Object item) (b) insertAtHead (c) insertAtTail (aka push back) (d) get(iterator here) (e) get(index i) (f) remove(iterator here)...
Match the following. Drag the appropriate labels to their respective targets. K << 1 Q <...
Match the following. Drag the appropriate labels to their respective targets. K << 1 Q < K Q = K Q >> 1 K approximately 1 Targets --------- reaction favors formation of more product --------- reaction will favor the formation of reactant _____ reaction is at equilibrium --------- reaction does not strongly favor reactants or products --------- reaction has a larger amount of product than reactants
Please explain what the Big O Notation is in plain English. Please include the logic behind...
Please explain what the Big O Notation is in plain English. Please include the logic behind it and calculations if necessary. I have trouble understanding it, I will be taking a test soon so I will need an easier way to remember it. I use Python btw.
What are Big-O expressions for the following runtine functions?      a) T(n)= nlog n + n...
What are Big-O expressions for the following runtine functions?      a) T(n)= nlog n + n log (n2 )        b) T(n)= (nnn)2           c) T(n)= n1/3 + n1/4 + log n      d) T(n)= 23n + 32n      e) T(n)= n! + 2n Write algorithm and program : Find the sum of the integers from 1 through n.     a)Use iterative algorithm and program         b) Use recursive algorithm and program. Order the following functions by growth rate:...
The following functions have been calculated as the runtime complexity of various algorithms. Identify the Big-O...
The following functions have been calculated as the runtime complexity of various algorithms. Identify the Big-O complexity, and provide witness values to support your answer. Clearly highlight your answer and show any working out you do. i. f(n) = 13 + 3n2 – 9n ii. f(n) = 3n.log2n + 7n iii. f(n) = nn + 2n5 – 7 iv. f(n) = 2log2n + 4n v. f(n) = 20 + 2n4 – n2 +n vi. f(n) = 7n3/4 +3n
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT