Ok, I did not know how the average case is calculated but I've assumed it would be O(N).

"Falls das Resultat nicht einfach nur dermassen gut aussieht, sollten Sie nochmal von vorn anfangen..." - Manual

Check out my new game: Pogostuck: Rage With Your Friends