Q:

time complexity of function in terms of Big-O notation?

1) Althoug i have studied about the big O notation i couldn't understand how we calculate the the time complexity of this function in terms of Big-O notation. Can you explain in detail.
2) For recursive function; why we call len-2 while using  recursive function ? 
bool isPalindrome( char *s, int len) {
             if (len <= 1) {
             return true;
        }
             else
            return ((s[0] == s[len-1]) && isPalindrome(s+1,len-2));
        }

What is the time complexity of this function in terms of Big-O notation?
T(0) = 1 // base case
T(1) = 1 // base case
T(n) = 1 + T(n-2)// general case
T(n-2)=1+T(n-4)
T(n) = 2 + T(n-4)
T(n) = 3 + T(n-6)
T(n) = k + T(n-2k) ... n-2k = 1  k= (n-1)/2
T(n) = (n-1)/2 + T(1)  O(n)

A:

You call the recursive function with len-2 because in each execution you remove 2 characters from the word(the first and last). Hence len-2.
T(n) = 1 + T(n-2) = 1 + 1 + T(n-4) = 1 + 1 + 1 + T(n-6) = n/2 + T(1) = O(n)
A function g(n) is O(f(n)) if there exists a constant c and a number n0 so that for n>n0 
g(n) < c*f(n).
The big-O notation is just an upper limit, so that function is O(n) but also O(n^2) and so on.

