I can find time complexity for 'for' loop but when the condition is changed I get stuck. Is there any mathematical way to calculate time complexity?

Question

Q1)

int a = 0, i = N; 

while (i > 0) { 
    a += i; 
    i /= 2; 
} 

Q2)

int i, j, k = 0; 

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

Answer 1

If you merely approach it mathematically, things can get very complex. most of the time it's better to walk through the logic of the algorithm.

Q1) i changes from N to 0. every time the loop runs, i (which was initially N) halves which gives you logarithmic time complexity. O(log N)

Q2) The outer loop runs n/2 times so O(N/2) and according to time complexity rules you drop the constant so O(N).

Every time the inner loop is run, you are doubling the value of j which means you are closing the distance between j and n in multiplications of 2 which is logarithmic so O(log N).

And since the inner loop runs for each element in the outer loop, the total time complexity is O(N log N).

And notice that I am not taking k = k + n / 2 and a += i into consideration because these operations run in constant time O(1) which is the least dominant time complexity and so has no effect in the calculations.