Question

2. Measure the complexity of the following algorithm: SHOW your work. (15 points) a=1 b 3: for (i = 0, i<= n, i++) d-d-1 for (j:0, j <= n, j++) c=a+b;

Answer 1

2.)

In above question we have two loops

Time complexity of a loop is given as either having incrementing values or decrementing values is O(n) where n is no of times the loop executes.

In above question we have two loops that is nested loop a loop within a loop

so for every iteration inner loop completes all its iterations

as outer loop is iterating 1 time inner loop iterates n times so when outer loop iterates n times inner loop also iterates making it n*n=n²

Hence the complexity of above one is O(n²)