Question

1- Find the time complexity of the following program, where n is given as input:

i = n;
while (i > 1) {
   j = i;
   while (j < n) {
      k = 0;
      while (k < n) {
         k += 2;
      }
      j *= 2;
   }
   i /= 2;
}

Express your answer using theta notation, and explain the amount of time it takes for each loop to finish.

Answer 1

******************************************************************************************
Please Upvote the answer as it matters to me a lot :)
*****************************************************************************************
As per HomeworkLib expert answering guidelines,Experts are supposed to answer only certain number of questions/sub-parts in a post.Please raise the remaining as a new question as per HomeworkLib guidelines.
******************************************************************************************

the k loop iterates for n/2 times so the complexity of K loop is O(n)

the j loop iterates for logn times so the complexity of J loop is O(log N) because the value of j is always double

the j loop iterates for logn times so the complexity of J loop is O(log N) because the value of j is always double

the i loop iterates for logn times so the complexity of I loop is O(log N) because the value of i is always divided by 2

so the overall complexity is O(nlog²n)