Time Complexity

Question

main()

{

int (b=1;b<=n;b*=2)

{

    for(i=0;i<b;i++)

        {

              for(j=0;j<n;j+=2)

                   {

                      sum+=j;

                    }

 

                  for(j=0;j<n;j*=2)

                   {

                      sum*=j;

                    }

            }

}

what is the complexity?

 

       }

Comments

O(n²) ?

---

ya how?

---

//C1
for(j=0;j<n;j+=2){
    sum+=j;
}
//C2
for(j=0;j<n;j*=2){
    sum*=j;
}

C1 code runs O(n/2) or O(n) and C2 code runs O(logn) --> As these are innermost codes so main contribution to time complexity is of C1 code i.e O(n).

Now situation is :

int (b=1;b<=n;b*=2){

    for(i=0;i<b;i++){
            
            //C1 running O(n)
    }
}

B values go like 1,2,4,8,16,32,...................,2^k(say)  after which loop breaks, inner i loop runs 1,2,4,8,16,....2^k times respectively for b values. So time complexity is (1+2+4..........+2^k )(n  [due to C1 code running in i loop] ) --> Now it can be solved !!

---

this is cbt2 QS ..:) I have solved it in exam btw.. adding solution.

Answer 1

@Gate Mission 1  is right.