TopCoder problem "SortEstimate" used in SRM 230 (Division I Level One , Division II Level Two)



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)
(be sure your method is public)
    
 

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.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3561

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6519&pm=3561

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , Olexiy

Problem categories:

Math, Search