How to estimate the execution time of an O( ) algorithm?

Question

C++ / C#

There is a task from the course CS50

Your implemenation must sort, from smallest to largest, the array of numbers that it’s passed.

Assume that each of the array’s numbers will be non-negative and less than 65,536. But the array might contain duplicates.

The running time of your implementation must be in O(n), where n is the array’s size. Yes, linear! Keep in mind that 65,536 is a constant.

You may not alter the function’s declaration. Its prototype must remain:

void sort(int values[], int n);

I wrote the job implementation like this:

void sort(int values[], int n)
{
    const int max = 65536;
    int array[max];
    //Заполняем массив нулями
    for(int i = 0; i < max; i++)
        array[i]=0;
    //Прибавляем еденицу к ячейке массива array, у которой индекс соответсвует значению values[i]
    for(int i = 0; i<n; i++)
        array[values[i]]++;
    //По порядку находим ненулевые ячейки, и по порядку присваиваем массиву values[] значения их индексов
    for(int i=0, j=0; i< max; i++)
        //учитываем так же вариант, в котором значения в массиве дублируются
        while(array[i]>0)
        {
            values[j]=i;
            j++;
            array[i]--;
        }
        return;
}

How can I now make sure that my algorithm actually runs in O(n) time?
Because intuitively it seems to me more complicated than insertion sort, which takes O(n^2) time:

for(int i=0; i<n-1; i++)
        for(int j=i+1; j>0 && values[j]<values[j-1]; j--)
            {
                int temp=values[j-1];
                values[j-1]=values[j];
                values[j]=temp;
            }

P.s. Is there any limit on asking questions? And then I think I'm already starting to bother with my noob questions here :)

Answer 1

How can I now make sure that my algorithm actually runs in O(n) time?

So to make sure:
Counter - n additions
Traversing the counter - constant (65k values)
Laying out sorted numbers - n assignments
---------
Total O(n)

Answer 2

What you wrote is called counting sort. The complexity is really O(n) since you are iterating over the original array only 1 time.
You also iterate 2 times over the fixed length array (65536).
The overall analysis looks like this:
65536 (padding with zeros) + N (traversing the source array to count elements) + 65536 (traversing the array of counters to write to the output, now sorted array) = 2*65536 + N = O(N + 2*65536) = O(N).
In the case of insertion sort, in the worst case, you do N operations (a rough estimate) for each of the N elements of the original array: N*N=N^2=O(N^2).