I want to find the time complexity of this function using repeating substition method . I know it goes something like this

T(n) = 2T(n/2) Θ(1) =2^2T(n/2^2) 2Θ(1) Θ(1) . . . =nΘ(1) (2^k-1)Θ(1)

and the result is O(n).I just don't understand why the end result is O(n). Where did it come from?

void foo(int n){ 
    if(n>1){ 
        foo(n/2); 
        foo(n/2);
    }
}

CodePudding user response：

Image the number