1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: TAOCP Exercise 5.1.1-6

  1. Nov 2, 2012 #1

    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.



    Attached Files:

  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted