Time and space complexity

#1

QUESTION 1 AND QUESTION 2

#2

Please paste the questions here.

#3

QUESTION 1.
Find the time complexity of the given code.
int count = 0;
for (int i = N; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count++;
QUESTION 2.
Find the Complexity of the given snippet.

   void function(int n) 
   { 
     int count = 0; 

     for (int i=0; i<n; i++) 
     for (int j=i; j< i*i; j++) 
         if (j%i == 0) 
         { 
            for (int k=0; k<j; k++) 
                 printf("*"); 
          } 
    }

IN Q2 THE LOOP OF K WILL RUN ATMOST N TIMES FOR i=N SO OVERALL COMPLEXITY should be O(n^4) and in question 1 it should be O(n*log n)

#4

For ques 1:
For a input integer n, the innermost statement is executed following times.

n + n/2 + n/4 + … 1
So time complexity T(n) can be written as

T(n) = O(n + n/2 + n/4 + … 1) = O(n)

The value of count is also n + n/2 + n/4 + … + 1

#5

For ques 2:
Consider the comments in the following function.

void function(int n)
{
int count = 0;

// executes n times
for (int i=0; i<n; i++)

// executes O(n*n) times. 
for (int j=i; j< i*i; j++) 
    if (j%i == 0) 
    { 
        // executes j times = O(n*n) times 
        for (int k=0; k<j; k++) 
            printf("*"); 
    }

}
Therefor time Complexity of the above function O(n^5)

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.