Алгоритм зацикливается до тех пор, пока m не достигнет 0. На каждой итерации m либо делится пополам (если оно было четным), либо уменьшается на 1 (если оно было нечетным). Если алгоритм будет просто делить пополам m на каждой итерации, то для этого потребуются шаги log (m) (в контексте сложности log () обычно подразумевает основу 2). В нашем случае, однако, у нас может быть не более двойного количества итераций, а именно, если после каждого деления пополам четного числа мы получим нечетное число. Эти нечетные числа уменьшаются на 1, что приводит к созданию следующего четного числа.
Удвоение количества шагов является постоянным фактором, который не учитывается при вычислении сложностей в нотации Big-O, поэтому сложность остается на уровне O (log (n)).