ビッグああ表記ループ操作

Question

は、それが全体的な概念はlog2nだろう意味ですか？ 外部ループが実行されるたびにnが変更されるため、内部ループは技術的にはlogn回実行されますが、ループはn回ループします。私はこの質問が愚かに聞こえるかどうか謝ります。これは、ループがどのように見えるかです：

outer loop runs while n>0 
    inner loops runs n times 
    n=(1/4)n 

私の書式設定がオフになっている場合、私は申し訳ありませんが、私はここで、ラテックスを使用する方法を把握しようとしている数分を費やし、かなりそれに

Answer 1

クラックができませんでした時間の複雑さはO(n)です：

First time, inner loop iterates n times 
Second time, inner loop iterates n/4 times 
Third time, inner loop iterates n/16 times 
... 
K'th time, inner loop iterates n/(4^k) times 

は、それらを総括：

n + n/4 + n/16 + ... + n/4^k + ... + n/(4^log_4(n)) 

はこれがありますsum of geometric series：

a = n 
r = 1/4 

そして、それの和がで囲まれている：r < 1