complexity-theory - 単純な除算の複雑さ

Question

（a）最悪の場合、（b）最良の場合、および（c）単純な除算を行う次の関数の平均的な場合の複雑さは何ですか

while n>=1 do
    n=n DIV 2
end {while}

複雑さをどのように正当化しますか？

Answer 1

関数は、正確に反復O(log n)する必要があるためです。floor(log2(n)) + 1