1

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';
        temp[k]++;
    }
    for (j = 0; j < m; j++)
    {
        k = p[j] - 'a';
        if (temp[k] > 0)
            temp[k]--;
        else
            break;
    }
    if (j == m)
        printf("string occured\n");
    else
        printf("not occured\n");
}

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

Improve this question
3
  • 1
    simple function, no recursion, no dynamic allocation: O(1)
    – ratchet freak
    Commented 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
    Commented 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
    Commented Jun 19, 2014 at 19:33

1 Answer 1

Reset to default
2

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.

Improve this answer
0

Your Answer

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

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