Complexity to find if there is a missing element in an array

Question

I am trying to write a function (in C) that checks if an array has all the elements (between 0 and its "size-1")

For example, if the array's size is 3, it should have {0, 1, 2 } in any order.

The question is: what is the most efficient complexity to do this without an extra array?

The complexity of my attempt, showed below, is (average of nlogn + n). edit: sorry for the miss understanding, any whole number can be an input, which means checking size wont work --> {0, 0, 3}

int check_missing_element(int *a, int n)
{
    int i = 0;

    quicksort(a, 0, n - 1);

    for (i = 0; i < n; i++)
    {
        if (a[i] != i)
            return 0;
    }

    return 1;
}

Answer 1

Walk the array using the value [0...n-1] of the element as the next element to visit.

As leaving each element, set its value to n. Any visited element with an n has already been visited and so is a failure - unless we have indexed ourselves. Any element with a value outside [0...n-1] is a failure.

After 'n' visits we are done. O(n).

Sort not needed. This does consume the array.