PROBLEM STATEMENT
You have implemented a sorting algorithm that requires exactly c*n*lg(n) nanoseconds to sort n
integers. Here lg denotes the base-2 logarithm. Given time nanoseconds, return the largest
double n such that c*n*lg(n) <= time.
DEFINITION
Class:SortEstimate
Method:howMany
Parameters:int, int
Returns:double
Method signature:double howMany(int c, int time)
NOTES
-lg(n) = ln(n)/ln(2) where ln denotes the natural log.
-Your return value must have a relative or absolute error less than 1e-9.
CONSTRAINTS
-c will be between 1 and 100 inclusive.
-time will be between 1 and 2000000000 inclusive.
EXAMPLES
0)
1
8
Returns: 4.0
Given 8 nanoseconds we can sort 4 integers since
1*4*lg(4) = 4*2 = 8
1)
2
16
Returns: 4.0
Now that c = 2 we need twice as many nanoseconds to sort 4 integers.
2)
37
12392342
Returns: 23104.999312341137
We can almost sort 23105 integers, but not quite.
3)
1
2000000000
Returns: 7.637495090348122E7
Largest possible return.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.