時間複雑度 - bigO表記

Question

def my_sum(i, j): 
    if i == j: 
     return i 
    mid = (i + j) //2 
    return my_sum(i, mid) + my_sum(mid + 1, j) 

なぜO(j - i)で、O(log n)ではないのですか？ (j >= i)

Answer 1

アルゴリズムは、再帰呼び出しごとにj-iを半分に分割します。再帰の深さは、i == jを得るために必要な再帰呼び出しの数で、各ブランチに対してlog2(j-i)になります。

だからアルゴリズムは、log2(j-i)の2の分岐係数、b有する再帰ツリー、および深さ、dを形成します。時間の複雑さは、ツリー内のアイテム数です。

b^d 
= 2^log2(j-i) 
= j-i