TAOCP Exercise 5.1.1-6

  • #1
Hi,

Knuth's TAOCP exercise 5.1.1-6 asks to construct an n-log-n algorithm which would generate an inversion table corresponding to a particular permutation.

My algorithm constructs inversion table for a random permutation of 1..N numbers (Knuth, Volume 3, exercise 5.1.1-6) using binary search tree where each node has two additional fields.


I'm trying to understand if my algorithm has complexity n-log-n not just theoretically but by observing performance data. Attached is the algorithm itself (Windows, C++, MinGW) and the resultant dataset which has two columns - first is size of the permutation and the second is the time it took to construct inversion table. I would appreciate if anybody could look into it, plot it in Excel and see if the curve in fact looks like it's n-log-n (I don't see it that way.)


Why am I seeing spikes in my data? Why is there this abrupt drop at datapoint 2070? If it has to do with the cache, can you suggest other programs/experiments clearly demonstrating how exactly spikes are related to cache? My processor is i7 quad core Bloomfield, three levels of cache, all 64 byte line size.

Thanks,

Monte
 

Attachments

  • InversionTable_TAOCP_5.1.1-6.zip
    51.6 KB · Views: 124

Answers and Replies

Related Threads on TAOCP Exercise 5.1.1-6

  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
23
Views
1K
  • Last Post
Replies
5
Views
2K
Replies
0
Views
481
  • Last Post
Replies
2
Views
670
Top