What is the complexity of halving the size of an $n$-bit number every time.

Question

I was discussing this question with my fiend the other day and was hoping to get some confirmation from someone if the logic I used is correct. Suppose that we have a number $N$ in base 2 ie $$N=2^n$$ where little n represents the number of bits of N. Correct me if I am wrong, but then I suppose that $$(N)^{1/2} = 2^{n/2}$$ which implies that $$N^{1/2}$$ is only n/2 bits in length. Furthermore, if we keep taking $\sqrt{N}$ until we reach 1, since the SIZE of $N$ decreases each time by 1/2, it takes $$O(\log_2n)$$ time and not $$O(\log_2N)$$ does that sound reasonable?

Answer 1

You are correct that taking a square root cuts the number of bits in half, so it will take of order $\log_2 (n)=\log_2( \log_2 (N))$ square root operations to get to $1$