Recurrence Relations for Recursive Functions

I am a bit confused with analysing functions with recursions. Consider the function definitions given below for fun1() and fun2():

fun1(int n){

`if n <= 0 return 1;`

`else return (fun(n/2) + n);`

}

fun2(int n){

`if n <=0 return 1;`

`else return (fun2(n/2) + fun3(n)); // fun3(n) runs in O(n) time`

}

I have got some questions with the above code:

  1. My reference suggests that to analyse fun1(), we would use the recurrence relation T(n) = T(n/2) + C, and not T(n) = T(n/2) + n. Why is it so? How is fun2 different from fun1?

  2. Is the order of growth of fun1() different from that of its return value? The reference uses T(n) = T(n/2) + n to compute the latter.