Part I. (30 pts) (10 pts) Let fin) and g(n) be asymptotically positive functions. Prove or...

Question

Question

Answer 1

Answer #1

(a) True

Because the complexity is considered as max of both of the functions.

So it is the time complexity of worst case, so it's true.

(b) False

it's not true let's take an example - f(n)=n and g(n)=n^2 so it doesn't gurantee as g(n)=Omega(f(n)), because it's the best case.

(c) This is true.

It can be written as O(c*(n)) or O(n), multiplication of a constant value doesn't matter.

(d) False.

In left hand side we have O(f(n)) that's the worst case.

and it's not neccesary that it will always be equal to average case .

(e) True.

for example -

any of the function's square will have upper bound for that particular function.

Answer 2

Similar Homework Help Questions

4. Let fín) and g(n) be asymptotically positive functions. Prove each of the following statements...

4. Let fín) and g(n) be asymptotically positive functions. Prove each of the following statements A. fin)-O(g(n)) if and only if fin) *gn)g(n)) B. fn) - Og(n if and only if fin)2- O(g(n)?) 4. Let fín) and g(n) be asymptotically positive functions. Prove each of the following statements A. fin)-O(g(n)) if and only if fin) *gn)g(n)) B. fn) - Og(n if and only if fin)2- O(g(n)?)
Let f1 and f2 be asymptotically positive non-decreasing functions. Prove or disprove each of the following...

Let f1 and f2 be asymptotically positive non-decreasing functions. Prove or disprove each of the following conjectures. To disprove, give a counterexample. a.If f1(n) = Theta(g(n)) and f2(n) = Theta(g(n)) then f1(n) + f2(n) = Theta(g(n)) b.If f1(n) = O(g(n)) and f2(n) = O(g(n))then f1(n) = O(f2(n))
Let f (n) and g(n) be asymptotically nonnegative functions. Using the basic definition of _-notation, prove...

Let f (n) and g(n) be asymptotically nonnegative functions. Using the basic definition of _-notation, prove that max( f (n), g(n)) = Θ( f (n) + g(n)).

Need help with 1,2,3 thank you. 1. Order of growth (20 points) Order the following functions...

Need help with 1,2,3 thank you. 1. Order of growth (20 points) Order the following functions according to their order of growth from the lowest to the highest. If you think that two functions are of the same order (Le f(n) E Θ(g(n))), put then in the same group. log(n!), n., log log n, logn, n log(n), n2 V, (1)!, 2", n!, 3", 21 2. Asymptotic Notation (20 points) For each pair of functions in the table below, deternme whether...
6) This question is part of Exercise 3-4 on page 62 of CLRS, but the letters...

6) This question is part of Exercise 3-4 on page 62 of CLRS, but the letters aren't all the same. Answer TRUE or FALSE for each of the following statements. TRUE means that the statement is TRUE for any asymptotically positive functions f(n) and g(n). Otherwise, answer FALSE. You don't have to Prove or Disprove these statements... but you should learn how to do that. f(n)- O( g(n)) implies g(n) O( f(n)) b) This is part a in Exercise 3-4....
Let f(n) = 5n^2. Prove that f(n) = O(n^3). Let f(n) = 7n^2. Prove that f(n)...

Let f(n) = 5n^2. Prove that f(n) = O(n^3). Let f(n) = 7n^2. Prove that f(n) = Ω(n). Let f(n) = 3n. Prove that f(n) =ꙍ (√n). Let f(n) = 3n+2. Prove that f(n) = Θ (n). Let k > 0 and c > 0 be any positive constants. Prove that (n + k)c = O(nc). Prove that lg(n!) = O(n lg n). Let g(n) = log10(n). Prove that g(n) = Θ(lg n). (hint: ???? ? = ???? ?)???? ?...

3. (10 pts) For each of the following functions f(n), prove the stated claim by providing...

3. (10 pts) For each of the following functions f(n), prove the stated claim by providing constants no C1, and c2 such that for all n2 no, cig(n) S f(n) or f(n) c2g(n), and provide a calculation that shows that this inequality does indeed hold (a) f(n) 2n2 3n3-50nlgn10 0(n3) O(g(n)) (b) f(n)-2n log n + 3n2-10n-10-Ω ( 2)-0(g(n))
1. (10 pts) For each of the following pairs of functions, indicate whether f = 0(g),...

1. (10 pts) For each of the following pairs of functions, indicate whether f = 0(g), f = Ω(g), or both (in which case f-6(1). You do not need to explain your answer. f(n) (n) a) n (b) n-1n+1 (c) 1000n 0.01n2 (d) 10n2 n (lg n)2 21 е) n (f) 3" (g) 4" rl. 72 i-0 2. (12 pts) Sort the following functions by increasing order of growth. For every pair of consecutive functions f(n) and g(n) in the...
4. (15 points) Prove or disprove each one of the following statements: ·0(f(n) + g(n)) =...

4. (15 points) Prove or disprove each one of the following statements: ·0(f(n) + g(n)) = f(n) + 0(g(n))I f(n) and g(n) are strictly positive for all n ·0(f(n) × g(n)) positive for all n f(n) 0(g(n))I f(n) and g(n) are strictly

10 points 4. One can obtain an asymptotically tight bound directly by computing a limit as...

10 points 4. One can obtain an asymptotically tight bound directly by computing a limit as n goes to infinity. Essentially, if the ratio of functions f(n) and g(n) converges to a positive constant as n goes to infinity, then f(n) e (g(n)). Let fand g be two functions that Lim f(n)/g(n) n0 exists and is equal to some number c > 0. Then f(n) 0 (g(n)) Prove the above statement