1) 8 marks] Give a big-O estimate for the number of operations, where an operati
ID: 3917133 • Letter: 1
Question
1) 8 marks] Give a big-O estimate for the number of operations, where an operation is a comparison, print or a multiplication, used in these segments of algorithms Ignore comparisons used to test the conditions in the while and for loops. a) while i0) for j- 0 to n-1 print (j) n=n/2 2) [12 marks a) Find a formula for 2n by examining the values of this expression for small values of n b) Prove the formula you conjectured in part (a) 3) [I0 marks Prove that for every positive integer n, (1x2) (2x3)+(nx(n+))- (nx(n+1)x(n+2) 3 4) [10 marks Which amounts of moncy can be formed using just two-dollar bills and five-dollar bills? Prove your answer using strong induction. 5) [0 marks] Find (2(3), and f(4) if fis defined recursively by f(0)--1.fl)-2, and for n-1,2 a) f(n+1)-+3(n I) 6) [10 marks] Assume fo is the nth Fibonacci number. Prove that fi+5++-f-when e is a positive integerExplanation / Answer
You can think big-O estimate in such a way that how many iterations you need to complete the code.
1: (a)while(i<n) print (i) i:= i*3
As we can see i is always multiplied by 3 so complexity would be O(log3N)
(b) As we can see the first time for loop will iterate N time than n will become n/2 then for the value of n it will iterate so we can see it is
n+ log2N + ---------- it is same as n + n/2 + n/4 + --- we can apply geometric formula and it will become 2n so complexity would be O(2N)
(c) The third one is also the same expect while loop will iterate one more time than it was in b part but it will not affect too much as in last its total iteration would be only 1 so the answer is O(2N)
2:(a)and (b) As we can see n/2+n/4+n/8 for any value let say 8 its value would be 4 + 2 +1 =7 approx same as O(N)(or you can think in such a way that in question 1(b) we found that n + n/2 + -- is 2N and now n is removed so it would be 2N-N= N as we can write as O(N)).
3: take a base case where n=1
LHS 1*2=2
RHS 1*2*3/3 =2
likewise prove for k and k+1
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.