PermCheck codility. O(N) time complexity

Question

Hi i have this solution for PermCheck codility. Here is the link which includes the question: https://codility.com/demo/results/demo73YNCU-8FK/

I got 100% for it but i got a time complexity of O(N * log(N)) or O(N). How could i make this code O(N)? Could you also give a brief description of what makes code O(N)? Thankyou.

Code here for shortcut:

    Array.Sort(A);
    if(A[0] == 1 && A.Length == 1) return 1;
    if(A[0] != 1) return 0;

    int n = 0;
    for(int i = 0; i < A.Length; i++)
    {    
        if(i < A.Length - 1)
        {
            if(A[i+1] == A[i] + 1)
            {
                n += 1;
            }
            else 
            {
                return 0;   
            }
        }

    }
    return 1;

Answer 1

Create a bool array which has the same size as the input, N, and leave all elements as the default false value. Loop through every element X of the input. If X is greater than N then return false. If array[N-1] is true, return false. Otherwise set array[N-1] to true. Repeat. This is O(N).

Explanation: First, if you have a permutation, then you need elements 1..N, but if any element is larger than N, then surely some elements are missing. Second, if an element occurs twice, it's a problem, that's why we create the bool array to remember already seen elements.