For positive ? the number of executions of count = count + 1 is representative of the complexity, as the other lines of code don’t execute significantly more times.
The recurrence relation can use the first iteration of the outer loop: that represents ? iterations of the inner loop. The loop continues for ?/2, and that can be represented with a recursive case:
?? = ? + ??/2
The base case is when ? is zero, in which case there is no iteration of the loop, or we could also set it when ? is one, in which case there is just one iteration of the loop:
?1 = 1
So this relation expands as follows:
?? = ? + ?/2 + ?/4 + … + 1 = ∑?=0..? (? / 2?)
This is a geomatric series that — when we perform integer divisions and ? is a power of 2 — is equal to 2?−1 and otherwise is not greater than 2?−1.
So we can say the algorithm has a complexity of O(2?) = O(?)
solved big O time complexity recurrence relation [closed]