時間の複雑さは

Question

次再帰関数の時間複雑

int DoSomething(int n){ 
    if(n<=2) 
     return 1; 
    else 
     return (DoSomething(floor(sqrt(n))) + n); 
} 

オプションにはどのようなものがあります。 -

1. はO（n^2）
2. O（n個のログn）//すべてのログは基数2です。
3. O（log n）
4. Oログログn

Answer 1

時間計算機能は、（それが漸近的に無関係であるようfloorを無視して）されています

私たちは、アルゴリズムが終了したときにmを見つける必要がある、すなわちとき：