Sorting method with Big-oh complexity


#1

A sorting method with “Big-oh” complexity 0(n logn) spends exactly 1 millisecond to sort 1000 data items.assuming that time T(n) of sorting n items is directly proportional to nlogn ,that is T(n)=cnlogn, derive a formula for T(n),given the time T(n) for sorting N items and estimate how long this method will sort 1,000,000 items.


#2

T(n) = c *n logn
=> 1 msec = c *1000 log(1000)
=> c = 1 / (1,000,000 * log1000)

Now,
T(n) = c * (1,000,000) log(1,000,000)
substitute the value of ‘c’, we get:
T(n) = 2 milli sec