I am attempting to calculate the big O notation for a simple recurrence relation $$T(n) = T(n/2) + 1\quad\text{when}\enspace n ≥ 1$$
$$T(1) = 1$$
So my attempt was as follows
$$T(n) \le T(\frac{n}{2}) + 1 \\ T(\frac{n}{2}) \le T(\frac{n}{4}) + 1 \\ ... \\ \\ T(n) + T(\frac{n}{2}) + T(\frac{n}{4}) + ... \le T(\frac{n}{2}) + T(\frac n4) + \dots + 1 + 1 + \dotsm\\$$
Since we can subtract $T(\frac n2), T(\frac n4)$ etc from both sides we can get
$$T(n) \le n \\ T(n) = T(\frac n2) + 1 \Rightarrow O(n)$$
But i was also given to understand that for recurrence relations the following stands:
$$T(n)=O(n^{\log_BA}), A > B^k \\ T(n)=O(n^k\log n),A=B^k \\ T(n)=O(n^k),A<B^k$$ Such that the recurrence relation is of the form $T(n)=AT(\frac nB) + O(n^k)$
If this were true would we not have the second case since $A=1 \; B=2 \ k =0$. So $1=2^0$So according to this the big O should be $O(n^0\log n)=O(\log n)$
Which one is right and why. Sorry for any formatting problems this is my first post.
For positive integer $n \geq 2$ we have $T(2^{n-1})=n $ by induction on $n$ . If $T(x)$ is defined for other values of $x$ and if $T$ is monotonic, then for $2^{n-1}<x<2^n$ we have $0<n=T(2^{n-1}\leq T(x) \leq T(2^n)= (n+1)$, so for all $x\geq 2$ we have $0<T(x)\leq 2+\log_2 x \leq 3 \log_2 x.$