What does θ(1) means in this equation?

Question

Hello I am trying to understand this recurrence equation with no success.

$ T(n) = T(n / 2) + θ(1)$

Base case : $T(1) = θ(1)$

and the solution is $θ(log_2 n)$.

What does $θ(1)$ stand for and why is the solution $θ(log_2 n)$?

Answer 1

So θ$(1)$ is a constant amount of time. Let's rename it as $k$ for simplicity's sake.

T(1) = k
T(2) = T(2 / 2) + k = T(1) + k = 2k
T(4) = T(4 / 2) + k = T(2) + k = 3k
T(8) = T(8 / 2) + k = T(4) + k = 4k
...
T(2^q) = T(2^ q-1) + k = q*k

So let's now say $ n = 2^q $ (which equals to $q = log2(n)$), then we have:

T(n) = log2(n) * k = log2(n) * θ(1) = θ(log(n))