I'm working on a problem where A is being decremented by the value of k in every iteration. K is also doubled in every iteration. So for example:
A = 30 -> 29 --> 27 --> 23 --> 15 --> 0 delta = 1 --> 2 --> 4 --> 8 --> 16
How can I assess the time complexity of this algorithm? I figure there has to be related to O(logN) due to the doubling of delta, but not sure how to intuitively/mathematically arrive at a conclusion.
The total size of N decrements is 2^N - 1 (prove this by induction), so from A, it takes ceil(log2(A + 1)) decrements to reach 0.
If the number is in between 2^n and 2^(n-1), i.e., 2^(n-1) <= A < 2^n, it will take exactly n steps to get to a non-positive value, since in n steps the total decrement is1+2+..+2^(n-1)=2^n-1 (use induction on n to prove). Hence, time complexity = n = lg 2^n = 1 + lg 2^(n-1) <= 1 + lg(A), where lg is log base 2.
