Question

1. (True or False) If f(n) = O(sqrt(n)) then f(n) = O(n), need explain 2. (True...

1. (True or False) If f(n) = O(sqrt(n)) then f(n) = O(n), need explain

2. (True or False) sqrt(n) = O(lg n), need explain

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

Homework Answers

Answer #1

1. True: yes this is true for the above expression.
Because O(n) is the upper bound for the sqrt(n) thus any expression which is greater than sqrt(n) would be applicable for this.

And sqrt(n) < n
Thus f(n) = O(n) is also correct.

2. False

For this, we need to see the graph for log(n) and sqrt(n).

As from the graph, it is clear that sqrt(n) > log(n) Thus log(n) = O(sqrt(n)) not the otherway arround, as sqrt(n) is the upper bound for the log(n).

That was a nice question to answer
Friend, If you have any doubts in understanding do let me know in the comment section. I will be happy to help you further.
Please like if you think effort deserves like.
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
True or False...Provide your reasons If f(n) =o(g(n)), then f(n)=O(g(n)) If f(n) =O(g(n)), then f(n) ≤...
True or False...Provide your reasons If f(n) =o(g(n)), then f(n)=O(g(n)) If f(n) =O(g(n)), then f(n) ≤ g(n) 3.  If 1<a=O(na), then f(n)=O(nb) 4. A and B are two sorting algorithms. If A is O(n2) and B is O(n), then for an input of X integers, B can sort it faster than A.
Determine wether the statements are true or false 1. Suppose we have f(n) = nlgn ,...
Determine wether the statements are true or false 1. Suppose we have f(n) = nlgn , g(n) = 5n , then f(n) = O(g(n)). 2. Suppose we have f(n) = nn/4 , g(n) = n1/2lg4n , then f(n) = O(g(n)). 3. No comparison-based sorting algorithm can do better than Ω(n log n) in the worst-case 4. Quicksort running time does not depend on random shuffling.
5 ^n+5 = O(5^n ) true or false show the procedure
5 ^n+5 = O(5^n ) true or false show the procedure
Assume that f(n) = O(g(n)). Can g(n) = O(f(n))? Are there cases where g(n) is not...
Assume that f(n) = O(g(n)). Can g(n) = O(f(n))? Are there cases where g(n) is not O(f(n))? Prove your answers (give examples for the possible cases as part of your proofs, and argue the result is true for your example).
Suppose T(n) is defined recursively as: T(0) = 1 T(n) = 3T(n-3) + O(n) True or...
Suppose T(n) is defined recursively as: T(0) = 1 T(n) = 3T(n-3) + O(n) True or false: T(n) ∈ O(2n)
Consider function f (n) = 3n^2 + 9n + 554. Prove f(n) = O(n^2) Prove that...
Consider function f (n) = 3n^2 + 9n + 554. Prove f(n) = O(n^2) Prove that f(n) = O(n^3)
Median of X~Par(2) is equal to sqrt(2) True or False please provide work
Median of X~Par(2) is equal to sqrt(2) True or False please provide work
True or False? If f : M → N is a homomorphism and a ∈ M,...
True or False? If f : M → N is a homomorphism and a ∈ M, then |a| = |f(a)|.
i) F o r t h e f o l l o w I n g...
i) F o r t h e f o l l o w I n g f i n d t h e ( c o m p. E x p.) f o u r I e r s e r i e s f o r x( t ) I I ) D r a w t h e am p &. P h a s e s p e c t r a I I I ) T...
Explain why each sequence diverges: {cos nπ} {1+(-1)^n} {sqrt(n)}
Explain why each sequence diverges: {cos nπ} {1+(-1)^n} {sqrt(n)}
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT