In the previous challenge, we counted the number of times the inner loop would be executed rather than just clamping it to n.
In this problem, if you make n=100 then the inner loop runs
[49 + 46 + 37 + 10] times
= (98/2) + (92/2) + (74/2) + (20/2)
= 100-(1+3^1) + 100-(1+3^2) + 100-(1+3^3) + 100-(1+3^4)
Which is bound to 3^(k+1)
And k is bound to cube root of n.
Thus, the overall complexity is bound to O(n).
Why did we just use log(n) x n/2?