Finding time complexity Big-Θ of this recursive formula involving floor function

Question

I am trying to find the time complexity (Big-Θ) of this algorithm:

Recursion(n):
   while n > 1:
      n = floor(n/2)
      Recursion(n)

I have found an upper bound of O(n) by considering the worst case which is when n is a power of 2.

However, I am having trouble finding a lower bound (Big-Ω) for this. My intuition is that this is Ω(n) as well, but I am not sure how to show this with the floor function in the way.

Any suggestions? Thank you!

EDIT: the main thing I'm not convinced of is that T(n/2) is equivalent to T(floor(n/2)). How would one prove this for this algorithm?

Answer 1

floor function performs its operation in constant time, O(1). Therefore you can ignore it/see it as a constant. Let's analyze the time complexity of the algorithm below:

T(n) = T(n/2) + 1 (floor operation)
T(n/2) = T(n/4) + 1
...
T(2) = T(1) + 1    --> T(1) = constant

T(n) = T(n/4) + 2
T(n) = T(n/8) + 3
...
T(n) = T(n/2^k) + k    2^k = n therefore k=log(n)
T(n) = T(1) + log(n)
T(n) = log(n)

We can conclude that T(n) ∈ θ(log(n)).