time complexity of randomized array insertion

So I had to insert N elements in random order into a size-N array, but I am not sure about the time complexity of the program

the program is basically:

for (i = 0 -> n-1){
    index = random (0, n); (n is exclusive)
    while (array[index] != null)
         index = random (0, n);
    array[index] = n
 }

Here is my assumption: a normal insertion of N numbers is of course strictly N, but how much cost will the collision from random positions cost? For each n, its collision rate increases like 0, 1/n, 2/n .... n-1/n, so expected number of insertions attempts will be 1, 2, 3 .. n-1, this is O(n), so total time complexity will be O(n^2), so is this the average cost? but wow this is really bad, am I right?

So what will happen if I do a linear search instead of keep trying to generate random numbers? Its worst case will obviously be O(n^2>, but I don't know how to analyze its average case, which depends on average input distribution?