What does time complexity actually mean?

Question

I got the task of showing the time taken by the merge sort algorithm theoretically ( n log(n) ) and practically (by program) on a graph by using different values of n and time taken.

In the program, I'm printing the time difference between before calling the function and after the end of the function in microseconds I want to know what dose n log(n) means.

I tryed with this values: Number of values: 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

program time in micro second: 12964 24961 35905 47870 88764 67848 81782 97739 111702 119682

time using n log n formula: 132877 285754 446180 611508 780482 952360 1.12665e+006 1.30302e+006 1.48119e+006 1.66096e+006

code:

auto start = std::chrono::high_resolution_clock::now();
mergeSort(arr, 0, n - 1);
auto elapsed = std::chrono::high_resolution_clock::now() - start;
long long microseconds = std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count();
cout << microseconds << " ";

Graph i got:

Answer 1

What time complexity actually means?

I interpret your question in the following way:

Why is the actual time needed by the program not K*n*log(n) microseconds?

The answer is: Because on modern computers, the same step (such as comparing two numbers) does not need the same time if it is executed multiple times.

If you look at the time needed for 50.000 and 60.000 numbers, you can see, that the 50.000 numbers even needed more time than the 60.000 numbers.

The reason might be some interrupt that occurred while the 50.000 numbers were sorted; I assume that you'll get a time between the 40.000 numbers and the 60.000 numbers if you run your program a second time.

In other words: External influences (like interrupts) have more impact on the time needed by your program than the program itself.

I got the task of showing the time taken by the merge sort algorithm theoretically (n log(n)) and practically (by program) on a graph by using different values of n and time taken.

I'd take a number of elements to be sorted that takes about one second. Let's say sorting 3 Million numbers takes one second; then I would sort 3, 6, 9, 12 ... and 30 Million numbers and measure the time.

This reduces the influence of interrupts etc. on the measurement. However, you'll still have some effect of the memory cache in this case.

You can use your existing measurements (especially the 50.000 and the 60.000) to show that for a small number of elements to be sorted, there are other factors that influence the run time.