How to find the time complexity?

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

• 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:

  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(n3). 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.)