Big Oh Notation and Bounding (Computer Science) Question 1) If f(n) is bounded b

Question

Big Oh Notation and Bounding (Computer Science)

Question 1) If f(n) is bounded by g(n) for all n > no, can f(n) be > g(n) when n < no ? Yes or no.

Question 2) If f(n) is bounded by g(n) for all n > no, can f(n) be > g(n) when n > no ? Yes or no.

Question 3) Consider the graph below. Is f(n) bounded by g(n)? Yes or no.

Question 4) Suppose algorithm A is O( n ) and algorithm B is O( n2). In theory, which algorithm should run faster, A or B?

Question 5) Suppose that you correctly implemented both algorithms. You found that for small problem sizes
the algorithm that is theoretically faster actually ran slower. You have not yet timed larger problem sizes.

Does that mean the theoretical prediction was wrong or useless? Explain in a sentence or two why or why not.

Explanation / Answer

Solution 1) Yes, f(n) is bounded by g(n) for all n>no means that only when n>no,g(n) will be larger than f(n),,otherwise for all n<no,f(n) will be larger than g(n).

Solution 2) No,f(n) will be larger than g(n) when n<no.

Solution 3) There is no graph available to the question 3 ("More Information needed").

Solution 4) Theoretically we can say that Algorithm A should run faster than Algorithm B,but one more thing is that It depends upon constant value,,for small constant values,it may be that O(n)(Algorithm A) take more time than O(n^2) (Algorithm B) to run.,but it is sure that for larger constant value,O(n) (Algorithm A) will run faster than O(n^2)(Algorithm B).

Solution 5) No,it doesn't mean that the theoretical prediction was wrong,Because for larger problem sizes,theoretically faster algorithm will run faster than the theoretically slower algorithm.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.