CS

How can i into Algorithm complexity analysis?

example:
How do i formally prove that the Binary Search is O(log(n)) on sorted arrays?

How fib(n) solved in a naive recursive way is O(2^n])?

Mathematically that's

Lets say i have a function:

(defun foo (n)
  (loop for i = 1 to (1- n) do
    (foo i)))

By simply trying out different n value it becomes clear this executes in O(2^ⁿ) time; however i have no clue how to prove it.

I could say:
T(1) = 1
T(N) = T(N-1)+T(N-2)+T(N-3)+...+T(1)
but i fail to comprehend masters theorem to apply it here.

Alternately i could draw a picture:

              |------------(foo 5)-|------------|----|
           (foo 4)--|           (foo 3)      (foo 2) (foo 1) 
           /     \ (foo 1)      /     \         |
        (foo 3) (foo 2)     (foo 2)   (foo 1)(foo 1)
        /     \       \         \
   (foo 2)   (foo 1)  (foo 1)   (foo 1)
      |
   (foo 1)


but that doesn't seem to really help me generalize this for n input