Time Complexity

Question

//n is a prime number here

int main()
{
    for(i=1;i<=n;i=2*i)
       {
             for(j=1;j<=n;j++)
               {
                 if(n%i==0)
                   {
                        k=1;
                      while(k<=n)
                        {
                       a=b+c;
                       k=k+1;
                        }
                   }
               }
         }
}

Comments

i think answer should be n^3

---

For i = 1 only, the statement if (n % i = 0) is true, for rest of the value of i, this statement is not true. as n is prime.

for i = 1 $\Rightarrow$ $n^{2}$ inner loop execute.

for i = 2 $\Rightarrow$ n times only.

for i = 4 $\Rightarrow$ n times.

for i = 8 $\Rightarrow$ n times.

....

....

for i = n $\Rightarrow$ n times.

T(n) = $n^{2}$ + n + n + n .... (log n) times n.

T(n) = $n^{2}$ + O(n(log n)).

T(n) = O($n^{2}$)

---

First loop:- Logn times

Second loop:- n times

Third loop will run only 2 times i.e for 1 and n as prime number has only two factors.

So nlogn+n should be time complexity

---

Case 1 ) n is some odd number

in that case if block will be able to execute when i=1 , otherwise it will always fail to execute as odd%even is always not zero value. so in that case we can analyze , TC as Hemant did. and output will be O(n²).

case 2 ) n is some even value

like suppose n=32

i=1 , j=1->n , k=1->n        : n² times

i=2 , j=1->n  , k=1->n       : n² times

i=4  ,j=1->n  , k=1->n       : n² times

i=8 ,j=1->n  , k=1->n        : n² times

i=16 , j=1->n  , k=1->n     : n² times

i=32 , j=1->n  , k=1->n     : n² times

so total n²logn times...

=> O(n²logn)

---

i never be equal to n . since n is prime number . @hemant sir

---

TC = O(n² log n) .

---

it will be O(n²)

for i=1 and i=n, it is running O(n²) times

for i = 2 , 4 , 8, 16, ......2^log(n-1) each, it is running O(n) times

overall time complexity = O(n²) + O(n²) + O(nlogn) = O(n²)

---

Change ur comment to answer @Hemant Parihar..

---

i incements as 1, 2, 4, 8, 16 ...  so we can observe that first loop executes till $\left \lceil logn \right \rceil$ (final value) 

Prime number gets divided by 1 and itself. Variable i ecounters only i = 1 so statement if (n % i == 0)  will only be true when i = 1

for (i = 1; i <= n; i = 2*i)   This loop will be executed log n times
for (j = 1; j <= n; j++)     This loop will be executed n * (log n) times
if (n % i == 0)                This statement will be executed n * (log n) times
k = 1;                             This statement will be executed n  times
while (k <= n)               This statement will be executed n² times 
a = b + c;                        This statement will be executed n² times
k = k + 1;                       This statement will be executed n²  times

Time complexity = O(n²)

---

we're talking about the worst case TC about this code segment , then won't the worst case would be when n=2^k and then as i'm abe to see TC would be n²logn .

see my comment and please tell me am i going wrong somewhere?

---

n is a prime number. How will it be 2^k

---

oops ! and i noticed it now. Thanks brother.

---

sir i think answer should b O(nlogn)

because first for loop run lgn(n) times

for second for loop j=1          while loop n times

                            j=2             1 time  because n%2==0 is false

                            j=3          1 time  because n%2==0 is false so.............

                           j=n            n times n%n==0 true

so total second loop=n+1+1+1.............+n=n-2+2n

and first loop log(n) times so O((3n-2)log(n))=O(nlog(n))

---

@Hemant Parihar ,when i =n then it will run n^2 .

---

@rahul

n is a prime number here. And i is getting double in each iteration. It never divide n properly when n > 2.