Show the time complexity of the following algorithms in terms of big-O. Assume print is a...

 

Transcribed Image Text:

Show the time complexity of the following algorithms in terms of big-O. Assume "print" is a constant time operation. Your big-O analysis should be as tight as possible to claim full credit (i.e., try to make it big- complexity). (a) k=1: for (i=0; i<n; i++) { for(j=0; j<n; j =j + k) print(A[j])); k = k * 2; (b) for (i = 1; i <n;i++) for (j =0; j<n; j = j + i) print (A[j]); You can assume n to be a power of 2. Also, to get a better under- standing of what these loops are doing, you might want to work them on an example array of size 8. Writing the time as a summation of mathematical series first and then bounding it might work. Show the time complexity of the following algorithms in terms of big-O. Assume "print" is a constant time operation. Your big-O analysis should be as tight as possible to claim full credit (i.e., try to make it big- complexity). (a) k=1: for (i=0; i<n; i++) { for(j=0; j<n; j =j + k) print(A[j])); k = k * 2; (b) for (i = 1; i <n;i++) for (j =0; j<n; j = j + i) print (A[j]); You can assume n to be a power of 2. Also, to get a better under- standing of what these loops are doing, you might want to work them on an example array of size 8. Writing the time as a summation of mathematical series first and then bounding it might work.