While finding time complexities I can find the time complexity of any loop but not able to proof or understand it mathematically for eg : for(i = 0 ; i > n ; i /= 2) have O(log n) but how can i find and proof it mathematically, Please help me to understand this.
Correciting the loop for(i = n ; i > 0 ; i /= 2)
First of all, I think the loop you want to ask about is this:
for (i = n; i > 0; i /= 2)
A simple empirical way to figure out the complexity is to simply relate the bound of the loop n to the number of times the loop executes. For example, if n = 16, then i would take the following values:
i | loop iteration
16 | 1
8 | 2
4 | 3
2 | 4
1 | 5
So for an input of n = 16, there are roughly 4 steps:
2^4 = n
log_2(n) = 4
=> number of iterations is log_2(n)