Insertion Sort

Jak widać sortowanie przez wstawianie dla tablicy posortowanej.
Wychodzi mi tutaj ok 0,384ms
Natomiast dla posortowanej odwrotnie ok 0,385ms

Czy jest to możliwe aby była tak mała różnica? Przecież to jest optymist i pesymistyczna zlozonosc czyli 0(n) i 0(n^2).

// Sortowanie Przez Wstawianie
 
#include <cmath>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>
#include <windows.h>
 
using namespace std;
 
const int N = 33333; // Liczebność zbioru.
 
 
int main()
{
  int d[N],i,j,x;
 
  cout << " Sortowanie przez wstawianie\n"
          "Przed sortowaniem:\n\n";
 
// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
 
 
 
  for(i = 0; i <= N; i++) d[i] = i;
  for(i = 0; i <= N; i++) cout << setw(4) << d[i];
  cout << endl;
 
// Sortujemy
 
 LONGLONG Frequency, CurrentTime, LastTime;
 double TimeScale;
 QueryPerformanceFrequency( (LARGE_INTEGER*) &Frequency);
 TimeScale = (1.0/Frequency)*1000.0;
 QueryPerformanceCounter( (LARGE_INTEGER*) &LastTime);
 
  for(j = N - 2; j >= 0; j--)
  {
    x = d[j];
    i = j + 1;
    while((i < N) && (x > d[i]))
    {
      d[i - 1] = d[i];
      i++;
    }
    d[i - 1] = x;
  }
 
QueryPerformanceCounter( (LARGE_INTEGER*) &CurrentTime);
 double milisec = (CurrentTime-LastTime)*TimeScale;
 printf(" %.4fms.",milisec);
// Wyświetlamy wynik sortowania
 
  cout << "Po sortowaniu:\n\n";
  for(i = 0; i < N; i++) cout << setw(4) << d[i];
  cout << endl;
 
 printf(" %.4fms.",milisec);
    system("PAUSE");
    return EXIT_SUCCESS;
}

Dla tablicy posortowanej odwrotnie mam zmieniony tylko ten fragment:

  
  for(i = N; i >0; i--) d[i] = i;
  for(i = N; i >0; i--) cout << setw(4) << d[i];
  cout << endl;
 

Nie mierz tak małych okresów, bo pewnie większy masz błąd pomiaru niż mierzony czas. Zmierz np. 10 000 iteracji żeby mieć czasy rzędu sekund a nie mikrosekund.

Odpowiedź jest banalna:
Po prostu nie tworzysz tablicy posortowanej odwrotnie (tylko posortowaną normalnie). Odwracasz tylko kolejność zapisywania wartości i ich wyświetlania na początku. W ogóle to czemu odwracasz kolejność wyświetlania? :P