how would i find the time and space complexity of this code?

Question

I am having difficulty finding space and time complexity for this code that i wrote to find number of palindromes in a string.

/**
 This program finds palindromes in a string.
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int checkPalin(char *str, int len)
{
    int result = 0, loop;

    for ( loop = 0; loop < len/2; loop++)
    {

        if ( *(str+loop) == *(str+((len - 1) - loop)) )
            result = 1;
        else {
            result = 0;
            break;
        }
    }

    return result;
}

int main()
{
    char *string = "baaab4";
    char *a, *palin;

    int len = strlen(string), index = 0, fwd=0, count=0, LEN;
    LEN = len;

    while(fwd < (LEN-1))
    {
        a = string+fwd;
        palin = (char*)malloc((len+1)*sizeof(char));    

        while(index<len)
        {
            sprintf(palin+index, "%c",*a);
            index++;
            a++;

            if ( index > 1 ) {
                *(palin+index) = '\0';
                count+=checkPalin(palin, index);
            }
        }

        free(palin);
        index = 0;
        fwd++;
        len--;
    }

    printf("Palindromes: %d\n", count);
    return 0;
}

I gave it a shot and this what i think:
in main we have two while loops. The outer one runs over the entire length-1 of the string. Now here is the confusion, the inner while loop runs over the entire length first, then n-1, then n-2 etc for each iteration of the outer while loop. so does that mean our time complexity will be O(n(n-1)) = O(n^2-n) = O(n^2)? And for the space complexity initially i assign space for string length+1, then (length+1)-1, (length+1)-2 etc. so how can we find space complexity from this? For the checkPalin function its O(n/2).
i am preparing for interviews and would like to understand this concept.
Thank you

Answer 1

Don't forget that each call to checkPalin (which you do each time through the inner loop of main) executes a loop index / 2 times inside checkPalin. Your computation of the time complexity of the algorithm is correct except for this. Since index gets as large as n, this adds another factor of n to the time complexity, giving O(n³).

As for space compexity, you allocate each time through the outer loop, but then free it. So the space complexity is O(n). (Note that O(n) == O(n/2). It's just the exponent and the form of the function that's important.)