Concept: comparing algorithms using order notation Assume the worst case and suf

Question

Concept: comparing algorithms using order notation Assume the worst case and sufficiently large input size unless otherwise indicated. The phrase the same time as means equal within a constamt factor (or lower order term) unless otherwise indicated. The phrase by a stopwatch means the actual amount of time needed for the algorithm to run to completion, as measured by a stopwatch 24. T or F: If f-(), then algorithm falways runs faster than g. 25. T or F: If f- (g), then algorithm falways runs faster than g, in all cases. 26. T or F: If f(g), then algorithm falways runs faster than g, regardless of input size. 27, T or F: If f = (g), then algorithmfalways runs faster than or takes the same time as g. 28. T or F: If f(g), then algorithm falways runs faster than or takes the same time as g, in all cases. 29. T or F: If fw (g), then algorithm falways runs faster than or takes the same time as g, regardless of input size 30, T or F: If f = (g), then it is possible that algorithmfcan run faster than g, in some cases. 31. T or F: If f(g), then it is possible that algorithm fcan run faster than g 32. T or F: If f = (g), then algorithmfalways runs slower than g. 33. T or F: If f = (g), then algorithmfalways runs slower thang, in all cases. 34. T or F: If f-(9), then algorithm falways runs slower than g, regardless of input size. 35. T or F: If f = (g), then algorithm,falways runs slower than or takes the same time as g. 36. T or F: If f = (g), then algorithm falways runs slower than or takes the same time as g, in all cases. 37. T or F: Iff = (9), then algorithm always runs slower than or takes the same time as g, regardless of input size 38. T or F: If f w (g), then algorithm fcan take the same time as g, in some cases 39. T or F: Iff = (g), then algorithm,fcan run in the same time as g.

Explanation / Answer

Let f(n) and g(n) be functions that map positive integers to positive real numbers. We say that f(n) is (g(n)) (or f(n) (g(n))) if for any real constant c > 0, there exists an integer constant n0 1 such that f(n) > c * g(n) 0 for every integer n n0

Hence by the above definition we can answer the true false questions

24.False as there can be a n where the algorithm is slow
25.False same as above
26.False as explained in 1
27.True it is possible that for some input it will take equal time
28.True
29 True as in 4 it is explained
30 True it is the lower bound
31 True
32 False as it is the lower bound
33 false
34 false
35 false The same reasoning applies for all
36 false
37 false
38 true
39 True
To most of the questions the same reasoning applies hence i have written the answers only
Basically what we have to understand is that it is the lower bound which is given by the little omega notation

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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