1. (a) Determine the asymptotic upper bound for the number of times the statement y=y +...

Transcribed Image Text:

1. (a) Determine the asymptotic upper bound for the number of times the statement "y=y + 1" is executed in each of the following algorithms. (b) (c) (i) (ii) i=1 while (i≤2n) { } (i) } else (ii) i=2 while (i <n) { Consider the following recursive algorithm. y=y+1 i=i+2 Algorithm G(n) if n ≤ 1 then result = n y=y+1 return result = 5.G(n-1)-6-G(n-2) Prove by induction on n that G(n) returns 3"-2" for all n > 0. For each of the following sums, determine its order of growth using the O(g(n)) notation with the simplest possible function g(n). 2n 2n 2n 3 32 33 i=1 j=1 +. 2n 3" 1. (a) Determine the asymptotic upper bound for the number of times the statement "y=y + 1" is executed in each of the following algorithms. (b) (c) (i) (ii) i=1 while (i≤2n) { } (i) } else (ii) i=2 while (i <n) { Consider the following recursive algorithm. y=y+1 i=i+2 Algorithm G(n) if n ≤ 1 then result = n y=y+1 return result = 5.G(n-1)-6-G(n-2) Prove by induction on n that G(n) returns 3"-2" for all n > 0. For each of the following sums, determine its order of growth using the O(g(n)) notation with the simplest possible function g(n). 2n 2n 2n 3 32 33 i=1 j=1 +. 2n 3"

Answer rating: 100% (QA)

1 a Asymptotic U... View the full answer