CODEWITHSUNDEEP
c#.netperformancealgorithmtime
Raheel Khan
Raheel Khan

Reputation: 14787

Calculate time for a logarithmic algorithm

I need to calculate the approximate amount of time an algorithm will take without actually running the code.

I cannot actually let the full algorithm run since it takes days or weeks to complete depending on hardware. The algorithm in logarithmic in nature. Following is an estimation of the algorithm. There is no logic included here of course.

We start with 2 raised to the power of [n] where [n] is large number.

int baseTwo = 2;
double log = 0D;
BigInteger number = 0;
double exponent = 5000000; // 5,000,000.

while (exponent > 0)
{
    number = BigInteger.Pow(baseTwo, (int) exponent); // [baseTwo]=2 raised to the power [exponent].
    number = this.ProcessNumber(number, baseTwo); // Returned number will be slightly smaller than what went in.
    exponent = BigInteger.Log(number, baseTwo); // The Base 2 Log to calculate the slightly decreased exponent (if exponent was 38762, then the result would be 38761.4234 for example).
}

private BigInteger ProcessNumber(BigInteger number)
{
    double rand = 0;
    BigInteger result = 0;

    rand = Random.Next(51, 100) / 100D; // Anywhere between 51% to 99%.
    result = number * rand; // [result] will always be less than [number] but more than half of [number].

    return (result);
}

Since the exponents are iterating towards zero, the time per iteration naturally decreases from one iteration to the next.

Upvotes: 2

Views: 462

Answers (2)

Penguino
Penguino

Reputation: 2176

Just the first and last iterations won't provide you with sufficient information, even if you know the limiting big-O efficiency of the algorithm, because there is no guarantee that the time per iteration will scale exactly to the limiting efficiency. For example, if your function was O(n^2) in the limit for large n (I know it isn't in this case - but this is just for the sake of illustation), but the actual time per step of real code was something like 1*log(n) + 10^-6*n + 10^-24*n^2, you might not see n^2 behaviour over the range of n you choose to look at. So you would have two points at the first and last iteration, but no way of knowing how to draw the line between them.

You could sample the data at regular intervals as you suggest, and then export it for fitting and/or numerical integration. But assumiong you only need to know the approximate total time (+/-10% perhaps) it should be suficient to do something along the lines of... Pseudo-code:

totaltime = 0;
for i := 0 to 5 do
begin
  starttime = now;
  for j := 0 to 10 do
    run algorithm(i*10^6+j)
  endtime = now;
  totaltime := totaltime + 10^5*(endtime - starttime);
  writeln('10 iterations near ', i*10^6, ' takes ', endtime - starttime, ' seconds');
end;
writeln('approximate time for complete algorithm to run is', totaltime);

.. and get an answer in less time than it has taken me to write this.

Upvotes: 3

user1277476
user1277476

Reputation: 2909

I'd suggest feeding your algorithm small but increasing inputs, and do a graph.

Curves on a graph can change all of a sudden, but they're probably still a better indicator than a lot of back-of-the-envelope calculations for something like this.

Upvotes: 1

Related Questions