here,for every valueof 'i',function call for foo(i) + all the function calls for numbers < i are considered.
lets suppose,we take, n=10
then
in first iteration, i=0 -> here just foo(0) is called.it takes 1 function call and it returns to for loop again.
in next iteration,then i=1 -> here we count foo(1) and then foo(0) (observe for loop carefully) hence,here 2 function calls are there
in next iteration, i=2 -> we call foo(2) -> foo(0) -> foo(1) ,now,1 function caall for foo(0) and for foo(1) ,there are already 2 function calls(see above).therefore,we require 4 function calls for i=2
in next iteration ,i=3 -> we call foo(3) -> foo(0) -> foo(1) -> foo(2) ,now 2 function calls for foo(1) and 4 function calls for foo(2)
,hence 8 function calls at i=3
solvind like this,we get 1+2+4+8+16+....n
finally we get,2n
so,T(n) for first part should be O(2n)
please verify this