このコードの実行時間は？それはn log nかnですか？

Question

私はdivide and conquerメソッドを使ってpow（a、n）を見つけるためにこのコードを書いています。私はこのコードの大きな複雑さについてはわかりません。それはnかnlog nですか？

pow(a,n) 
{ 
    if n->1 return a 
    i<-floor(n/2) 
    j<-ceil(n/2) 
    return pow(a,i) * pow(a,j) 
} 

また、この場合の乗算である合成ステップの複雑さは何ですか？それは1かnか？

Answer 1

pow(a,n)を呼び出すたびにpow(a,n/2)が〜2コールされるため、おおよそO（n）です。