Assume the worst case and sufficiently large input size unless otherwise indicat

Question

Assume the worst case and sufficiently large input size unless otherwise indicated. The phrase the same time as means equal within a constant 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 = a(g), then algorithm f always runs faster than g 25. T or F: If f a(g), then algorithmf always runs faster than g, in all cases 26. T or F: If f a(g), then algorithmf always runs faster than g, regardless of input size 27, T or F: If f-w(g), then algorithm f always runs faster than or takes the same time as g 28. T or F: If f = w(g), then algorithmf always runs faster than or takes the same time as g, in all cases. 29, T or F: If f = w(g), then algorithm f always runs faster than or takes the same time as g, regardless of input size. 30. T or F: If f(9), then it is possible that algorithm f can run faster than g, in some cases 31, T or F: If f = a(9), then it is possible that algorithm f can run faster than g 32. T or F: If f = a(g), then algorithm f always runs slower than g 33. T or F: If f = a(g), then algorithrn f always runs slower than g, in all cases 34. T or F: If f-w(g), then algorithm f always runs slower than g, regardless of input size 35, T or F: If f = w(g), then algorithm f always runs slower than or takes the same time as g 36. T or F: If f = ?(g), then algorithm f always runs slower than or takes the same time as g, in all cases 37, T or F: If f = w(g), then algorithm f always runs slower than or takes the same time as g, regardless of input size 38. T or F: If fw(g), then algorithm f can take the same time as g, in some cases 39. T or F: If f(g), then algorithm f can run in the same time as g 40, T or F: If f-S2(g), then algorithrn f always runs faster than 41. T or F: If f-?(g), then algorithmf always runs faster than g, in all cases 42. T or F: If f-9(g), then algorithm f always runs faster than g, regardless of input size

Explanation / Answer

we say that f(n) = O(g(n)) when there exist constants c > 0 and n0 > 0 such that

f(n) <= c * g(n), for all n >= n0

this means that function f(n) does not grow faster than g(n), or that function g(n) is an upper bound for f(n), for all sufficiently large n-> infinity

So, by above defintion

f=w(g) means g grows faster than f for larger inputs

So)

24) F (reversely given so wrong)

25)F ( reverse)

26,27,28,29) F (same explanation)

30) T (because according to our definiton, G runs faster than F especially for larger inputs, So, for small inputs F may sometimes runs faster than G, So True)

31) F (because if input size is not mentioned,we have to take large input, so it is false for large inputs)

32) T (input size not mentioned, so take large inputs, so true)

33) F (here given in all cases, so we have to consider both small inputs and large inputs, so for large inputs ,it is true, but for small inputs , f may sometimes run faster than g, so false)

34) F (same explanation as above)

35) T (consider inputs as only large input since it is not mentioned, so true as f <= c*g)

36) F ( consider small inputs,f may run faster than g , so false)

37) F (same explanation as above)

38) T (in some cases it may true because f<= c*g)

39)F ( input not given so take large inputs, but for large inputs , g(n) is an upper bound for f(n) , so false)

We say that f(n) = ?(g(n)) when there exist constant c that f(n) >= c*g(n) for for all sufficiently large n.

40) T (input not mentioned so take large inputs, so f runs faster than g always)

41)F (in all cases given, for large inputs it is true , but consider for small inputs, f may run slower than g , so false)

42) F (same explanation as above)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---