Question: You are given this algorithm for input of size n , with the lines numbered: 1 : result = 0 2 : i = 1

You are given this algorithm for input of size n, with the lines numbered:
1: result =0
2: i =1
3: while i < n:
4: j =1
5: while j < n:
6: result = result + j
7: j = j *2
8: i = i +2
9: return result
a) Using big-O, how many times will line 8 of this algorithm be executed? Justify your answer.
b) Using big-O, how many times will line 6 of this algorithm be executed? Justify your answer.
c) Using big-O, what is the time complexity of this algorithm? Justify your answer.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!