0

I am trying to generate runtimes for this fibbonacci series program for iterative algorithm and after generating the fibbonacci number for almost 25k values, the runtime taken is staying constant for some reason. Is this because of the subprocess call I am using in python script or something else?

Python Script to run the program and record time:

start = time.time()
subprocess.run(command, timeout=TIMEOUT)
end = time.time()
result = end - start

C Program:

unsigned long long first = 0, second = 1, result;

    if (n <= 1) return n;

    for (int i = 0; i < n; i++)
    {
        if (i <= 1)
            result = i;
        else
        {
            result = first + second;
            first = second;
            second = result;
        }
    }
    return result;

I tried to change the number of values to a lot more and it still stays constant. This algorithm should be O(n). Right now I am getting values around 0.00200 seconds, It doesnt go above 0.003 and below 0.001.

Tom Karzes
  • 22,815
  • 2
  • 22
  • 41
Neel Patel
  • 1
  • 1
  • Not sure why you're getting those results, but as a starter, you can look into [using timeit module instead of time](https://stackoverflow.com/questions/17579357/time-time-vs-timeit-timeit) to measure the performance of code in python, you will get more accurate results – Florent Monin Mar 03 '23 at 08:50
  • 4
    The running time of the C program is probably negligible compared to the rest of the execution. – Thierry Lathuille Mar 03 '23 at 08:57
  • 1
    You're going to overflow `unsigned long long` very quickly. – user2357112 Mar 03 '23 at 08:59
  • 1
    Note that the 25000th term of the Fibonacci sequence requires more than 17000 bits (it has 5225 decimal digits), so yes, you overflowed a long time ago... – Thierry Lathuille Mar 03 '23 at 09:01
  • 2
    What is `n`? Your code is way too incomplete to tell what happens. If all limits are available as constants during runtime the compiler might even calculate the result and drop the whole loop. – Gerhardh Mar 03 '23 at 09:01
  • If you let your value go above 10^12 or even 10^24 (avoiding overflow, obviously), I believe your runtime might start increasing :-) – Dominique Mar 03 '23 at 09:03
  • Note also that your expectation to have O(n) runtime doesn't take into account the growing size of the numbers if you want their exact integer values, so you have to expect something slower than O(n) in reality. – Thierry Lathuille Mar 03 '23 at 09:05
  • @Gerhardh I am running a command to execute my C program and passing in command line arguement for the N (Number till which I want to calculate fibbonacci sequence). Since that is available during runtime, does that mean it directly just calculates and never runs the loop? That would explain the constant runtime. – Neel Patel Mar 03 '23 at 09:19
  • 1
    Sorry, that was a typo. I meant available at compile time. If you provide as parameter, it cannot be optimized in that way. – Gerhardh Mar 03 '23 at 09:26

0 Answers0