1. There is a function that is both O(n^2) and Omega(n^3). 2. Given two functions f(n) and g(n), if g(n)=O(f(n)) and f(n)=O(n^2), then g(n)=O(n^5). 3. Given two functions f(n) and g(n), if g(n)=O(f(n)) and f(n)=O(n^2), then g(n)=Omega(n).

Ruby Briggs 2022-07-17 Answered
1. There is a function that is both O ( n 2 ) and Ω ( n 3 ).
2. Given two functions f(n) and g(n), if g ( n ) = O ( f ( n ) ) and f ( n ) = O ( n 2 ), then g ( n ) = O ( n 5 ).
3. Given two functions f(n) and g(n), if g ( n ) = O ( f ( n ) ) and f ( n ) = O ( n 2 ), then g ( n ) = Ω ( n ).
I think the first one is false, but not sure about other two. Can anyone help me?
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Jorge Franklin
Answered 2022-07-18 Author has 11 answers
Step 1
You’re right about the first one; I’ll prove it. Then I’ll point you in the right direction for the other two; see if you can finish them on your own, but if you get stuck, feel free to leave a comment.
1. Suppose that f(n) is both O ( n 2 ) and Ω ( n 3 ). Then there are positive constants c 1 and c 2 and an m N such that | f ( n ) | c 1 n 2 and | f ( n ) | c 2 n 3 for all n m. But then for all n m we must have c2n3≤|f(n)|≤c1n2and hence n m, which is clearly false when c 2 n 3 | f ( n ) | c 1 n 2 . Thus, there is no such f(n): you were correct.
2. The hypotheses imply that there are c 1 , c 2 > 0 and m N such that | g ( n ) | c 1 | f ( n ) | and | f ( n ) | c 2 n 2 for all n m. Can you find an inequality relating |g(n)| to n 2 ? What about to n 5 ?
3. What if f and g are both constant functions?
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2020-11-09
Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.
asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2021-08-18

Discrete Mathematics Basics

1) Find out if the relation R is transitive, symmetric, antisymmetric, or reflexive on the set of all web pages.where (a,b)R if and only if 
I)Web page a has been accessed by everyone who has also accessed Web page b.
II) Both Web page a and Web page b lack any shared links.
III) Web pages a and b both have at least one shared link.

asked 2021-08-03

A 5-card hand is dealt from a perfectly shuffled deck of playing cards. What is the probability that the hand is a full house? A full house has three cards of the same rank and another pair of the same rank. For example, {4, 4, 4, J, J}

asked 2022-09-07
"Let m, n, and r be non-negative integers. How many distinct "words" are there consisting of m occurrences of the letter A, n occurrences of the letter B, r occurrences of the letter C, such that no subword of the form CC appears, and no other letters are used?"
asked 2022-07-15
Here is an equivalence relation R = { ( x , y ) | x y } is an integer}
My question is: what is the equivalence class of 1 for this equivalence relation?
Can say indicate the equivalence class of 1 as [ ( 1 ) ] = { ( x , y ) , x y = }
I am confused about how to write the right hand side? can someone help me?

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question