Question

In: Computer Science

Prove the following problems. 1 .Use the definition of big O to explain why or why...

Prove the following problems.

1 .Use the definition of big O to explain why or why not 3/(x2 + 3x) = O(3). Prove your answer.

2 .Use the definition of  Θ to explain why or why not sqrt(2 + sqrt(3x)) =  Θ(x1/4). Prove your answer.

3 .Explain why 5x2 =  Θ(2x2) is true and  5x2 ~ 2x2 is not true.

Solutions

Expert Solution


Related Solutions

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)...
1. For each of the following, prove using the definition of O(·): (a) 7n + log(n)...
1. For each of the following, prove using the definition of O(·): (a) 7n + log(n) = O(n) (b) n2 + 4n + 7 = O(n2 ) (c) n! = O(nn) (d) 2n = O(22n) Please explain the procedure clearly for all (They are of the same question)
Justify the following statements using the "big-Oh" definition: a) (n+25)2 is O(n2) , and n2 is...
Justify the following statements using the "big-Oh" definition: a) (n+25)2 is O(n2) , and n2 is O((n+25)2) b) n3 is NOT O(n2); c) Given f1(n) is (n+25)2 , and f2(n) is n3 what is the big-Oh for f1(n) x f2(n)?
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...
1. Use the definition of convexity to prove that the function f(x) = x2 - 4x...
1. Use the definition of convexity to prove that the function f(x) = x2 - 4x + 8 is convex. Is this function strictly convex? 2. Use the definition of convexity to prove that the function f(x)= ax + b is both convex and concave for any a•b ≠ 0.
1A) Let ?(?) = 3? + 2. Use the ? − ? definition to prove that...
1A) Let ?(?) = 3? + 2. Use the ? − ? definition to prove that lim?→1 3? + 2 ≠ 1. Definition and proof. 1B) Let ?(?) = 2?^2 − 4? + 5. Use the ? − ? definition to prove that lim?→−1 2?^2 − 4? + 5 ≠ 8. definition and ? − ? Proof.
(a) Explain the difference between big-O and big-theta, and give examples of each to show the...
(a) Explain the difference between big-O and big-theta, and give examples of each to show the difference. (b) How can we say that two functions have the same asymptotic complexity, using big-theta notation? (c) Rank the following functions in order of increasing complexity (rate of growth), and indicate which functions have the same asymptotic complexity. x2; x log(x); 2x; log(x) + 7; 92x2 + 57x + 3921; 4x; 27x2 + 8x3; 22x+5; log(x42); 3x + 12.
1. Use the ε-δ definition of continuity to prove that (a) f(x) = x 2 is...
1. Use the ε-δ definition of continuity to prove that (a) f(x) = x 2 is continuous at every x0. (b) f(x) = 1/x is continuous at every x0 not equal to 0. 3. Let f(x) = ( x, x ∈ Q 0, x /∈ Q (a) Prove that f is discontinuous at every x0 not equal to 0. (b) Is f continuous at x0 = 0 ? Give an answer and then prove it. 4. Let f and g...
Use the definition of absolute value and a proof by cases to prove that for all...
Use the definition of absolute value and a proof by cases to prove that for all real numbers x, | − x + 2| = |x − 2|. (Note: Forget any previous intuitions you may have about absolute value; only use the rigorous definition of absolute value to prove this statement.)
1) “Big problems, big opportunities; small problems, small opportunities.” Now it is your turn to identify...
1) “Big problems, big opportunities; small problems, small opportunities.” Now it is your turn to identify some problems you encounter in your job or daily life and think about whether you may solve them by developing a new product or service. Please also think about how your solution(s) may take advantage of trends in economic, social, technological and political sectors. 2) Spend some time studying Yammer (www.yammer.com) which is an enterprise social network. Please share with the class your opinion...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT