I have written my version of strstr function in c. I am using a temporary array of size 26. Then is the space complexity O(1) or O(n)? This is my code :

void strcheck(char t[], int n, char p[], int m)
    int i, j, k;
    int temp[26];

    for (i = 0; i < 25; ++i)
        temp[i] = 0;
    for (i = 0; i < n; ++i)
        k = t[i] - 'a';
    for (j = 0; j < m; j++)
        k = p[j] - 'a';
        if (temp[k] > 0)
    if (j == m)
        printf("string occured\n");
        printf("not occured\n");

The program is working correctly just wanna know about space complexity. Thanks

  • 1
    simple function, no recursion, no dynamic allocation: O(1) Jun 19, 2014 at 17:50
  • Nothing in your code takes different amounts of space depending on n (or any other variable for that matter).
    – user7043
    Jun 19, 2014 at 17:52
  • FYI, your function does not do exactly as strstr, e.g. if you called strcheck with "omer" as t and "rome" as p, I think it will still state that the string occurred. If that's your intention, then you're good.
    – Omer Iqbal
    Jun 19, 2014 at 19:33

1 Answer 1


This is using O(1) (also Big-Theta(1), as the best-case and worst-case use are the same figure) space-complexity as the the amount of space needed to perform the operation does not increase with n.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.