Question

Algorithm problem b. Give an example of a single nonnegative function ƒ(n) such that for all...

Algorithm problem

b. Give an example of a single nonnegative function ƒ(n) such that for all functions g(n) in part (a), ƒ(n) is neither in O(g(sub(i))(n)) nor in Ω(g(n)).

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

f(n)=0 if n is even

f(n)=n^(n^n) if n is odd

The above function has basically 2 parts which means that if n is even then it will make sure f(n) is not greater than g(n). So, it can't be Omega(g(n)).

If n is odd it is the function with more complexity of all listed in a part. So, this will confirm that it will be never less than g(n). So, f(n) can't be O(g(n))

Kindly revert for any queries

Thanks.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
For all of the problems below, when asked to give an example, you should give a...
For all of the problems below, when asked to give an example, you should give a function mapping positive integers to positive integers. Find (with proof) a function f_1 such that f_1(2n) is O(f_1(n)). Find (with proof) a function f_2 such that f_2(2n) is not O(f_2(n)). Prove that if f(n) is O(g(n)), and g(n) is O(h(n)), then f(n) is O(h(n)). Give a proof or a counterexample: if f is not O(g), then g is O(f). Give a proof or a...
For all of the problems below, when asked to give an example, you should give a...
For all of the problems below, when asked to give an example, you should give a function mapping positive integers to positive integers. Find (with proof) a function f_1 such that f_1(2n) is O(f_1(n)). Find (with proof) a function f_2 such that f_2(2n) is not O(f_2(n)). Prove that if f(n) is O(g(n)), and g(n) is O(h(n)), then f(n) is O(h(n)). Give a proof or a counterexample: if f is not O(g), then g is O(f). Give a proof or a...
1.Let f and g be two functions such that f(n)/g(n) converges to a positive value less...
1.Let f and g be two functions such that f(n)/g(n) converges to a positive value less than 1 as n tends to infinity. Which of the following is necessarily true? Select one: a. g(n)=Ω(f(n)) b. f(n)=Ω(g(n)) c. f(n)=O(g(n)) d. g(n)=O(f(n)) e. All of the answers 2. If T(n)=n+23 log(2n) where the base of the log is 2, then which of the following is true: Select one: a. T(n)=θ(n^2) b. T(n)=θ(n) c. T(n)=θ(n^3) d. T(n)=θ(3^n) 3. Let f and g be...
Problem 2 (a) Describe how one can visually identify the graph (or table) of a function...
Problem 2 (a) Describe how one can visually identify the graph (or table) of a function f which satisfies the property f(x) = f(−x) for all numbers x in the domain of f. (b) Describe a function g which satisfies the property g(x) = −g(x) for all numbers x in the domain of g. Problem 3 (a) If the average rate of change between two points on a linear function is positive, is the function increasing between those two points?...
1 (a): Give an example that shows the greedy algorithm that picks the item with largest...
1 (a): Give an example that shows the greedy algorithm that picks the item with largest profit first (and continues in that fashion) does not solve the 0 − 1 Knapsack problem. 1 (b): Give an example that shows the greedy algorithms that picks the object with largest profit first (and continues in that fashion) does not solve the Fractional Knapsack problem. Please show your work! I will rate quality answers. Thank you!
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm that is executed most frequently. Express the number of times it is executed as a function of N. Convert this expression into the Big-O notation. A. For each of the three fragments of code, what is its worst-case time complexity, in the form "O(…)". (Use the given solution to the first problem as a model)                 //----------------- This is a sample problem – solved ------...
In this problem your task is to find a missing number. The input will always consist...
In this problem your task is to find a missing number. The input will always consist of an array of n positive integers such that the difference between every two consecutive numbers is a fixed constant but one integer is missing. See below for two example inputs/outputs: Input sequence: [0, 2, 4, 6, 10] Output: missing number is 8 Input sequence: [1, 4, 7, 13, 16] Output: missing number is 10 Note that in the first example the constant c...
For each problem below, either give an example of a function satisfying the give conditions, or...
For each problem below, either give an example of a function satisfying the give conditions, or explain why no such function exists. (a) An injective function f:{1,2,3,4,5}→{1,2,3,4} (b) A surjective function f:{1,2,3,4,5}→{1,2,3,4} (c) A bijection f:N→E, where E is the set of all positive even integers (d) A function f:N→E that is surjective but not injective (e) A function f:N→E that is injective but not surjective
Are any of the following implications always true? Prove or give a counter-example. a) f(n) =...
Are any of the following implications always true? Prove or give a counter-example. a) f(n) = Θ(g(n)) -> f(n) = cg(n) + o(g(n)), for some real constant c > 0. *(little o in here) b) f(n) = Θ(g(n)) -> f(n) = cg(n) + O(g(n)), for some real constant c > 0. *(big O in here)
Problem 1. (1 point) The SolEc algorithm shown below is used with a = 0, b...
Problem 1. (1 point) The SolEc algorithm shown below is used with a = 0, b = 2 and n = 3. What is the value of c on the line Write c? Function z <- f (x) z = 85−99x + 15x2 − x3; End Function algorithm SolEc Read a, b, n; For i From 1 To n Do c = (a + b) / 2; Write a, ",", c, ",", b; If f (a) * f (c) <0...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT