Its important to define recursion complexity in terms of recurrence relations.
For your first algorithm, you have
T(n) = T(n-1) + O(1)
Which means you do some constant amount of work, and decrease the size of your set by 1 and recursively call yourself. This will yield a recursion tree of depth n
, where each parent only has one child (you can think of it as a straight line), which you can see would be O(n) because of the constant amount of work.
For the second algorithm, you have
T(n) = 2T(n/2) + O(1)
Saying you split your input in half and call recursively twice, and do some constant amount of work. This scenario you can use the master thereom to show it is O(n)
.