LOOP_CMPL2

What is the time complexity of the following code :

    int i, j, k = 0;
    for (i  = n/2; i <= n; i++) {
        for (j = 2; j <= n; j = j * 2) {
            k = k + n/2;
        }
    }

•  Θ(n)
•  Θ(nLogn)
•  Θ(n^2)
•  Θ(n^2 / Logn)
•  Θ(n^2Logn)

Good solution:

let me discuss it on the code let’s take n = 1024 which is equal to 2^10

k = k + n/2;

here we are looping from j =2 to n and increment by 2 so
in case j=2 so next j = 4 then j =4*2= 8 then 16 , 32 , 64 ,128 , 256 , 512 till 1024 which is 2 ^1 - 2^2 - 2^3 - 2^4 -2^5 - 2^7- 2^6 - 2^8 - 2^9- 2^10
so if you count the number of this statement can run for n= 1024 will be 10 and log1024 = 10

Log 1024 = log 2^10 = 10 * log2 = 10*1
Log2 base 2 = 1

so the time for this will be O(nlogn)