-2
    #include <stdio.h>
    
    int fib_iter(int n)
    {
       if(n == 0) return 0;
       if(n == 1) return 1;
     
       int pp = 0;
       int p = 1;
       int result = 0;
    
       for(int i = 2; i <= n; i++)
       {
          result = p + pp;
          pp = p;
          p = result;
       }
       return result;
    }
    
    int main(void)
    {
        int m;
        printf(" Get Fibonacci\n");
        printf("Enter an integer for m = ");
        scanf_s("%d", &m);
        if (m < 0) return 1; 
        for(int i = 0; i <= m; i++)
        {
           printf("fib(%d) = %d\n", i, fib_iter(i));
        }
        return result;
    }

Program above was coded to print out Fibonacci numbers like fib(0), fib(1), ...fib(m). What is the Time Complexity of this program according to integer m described with Big-O notation? Explain why. (Let's say the time calculation for printf() functions are ignored. The console output for integer m does not allow any number bigger than INT_MAX. Therefore, ignore the overflow.)

Should the answer be O(m) or O(m^2)?

Lee
  • 21
  • 4
  • "Therefore, overflow never happens" AHAH... fibonacci numbers grow with the ratio (approx) 1.6. It only takes about 93 terms to reach INT_MAX (in 64-bits) (1.6^93=2^64) – pmg Jul 17 '20 at 11:41
  • I changed the question. Could you do me a favor and answer the question please.... I need to know the time complexity – Lee Jul 17 '20 at 11:45
  • I have no school knowledge of O notation... Your `fib_iter` has a loop to `n`, your main function has a loop to `m` ... ==> therefore the whole thing is `O(mn)`, so less than `O(m^2)` but the difference mught be negligible. I'd say O(m^2) :) – pmg Jul 17 '20 at 11:48
  • But the question says printf() functions are ignored. Therefore, isn't the printf() function in the for loop of the main() function as well be ignored totally? Because the fib_iter() function is included in printf(). – Lee Jul 17 '20 at 11:55
  • If you account for `printf()` (again, I have no formal learning in O notation) it would be `O( * m^2)` which is equal to `O(m^2)` but the O notation is not relevant for something that loops less than 100 times! – pmg Jul 17 '20 at 12:00
  • Unrelated: `if (n == 0) return 0; if (n == 1) return 0;`-> `if (n == 0 || n == 1) return 0;` or just `if (n < 2) return 0;`. `int n` also could be changed to `unsigned int`. – RobertS supports Monica Cellio Jul 17 '20 at 12:02
  • Computing `fib(n)` takes O(n) arithmetic operations. You compute `fib(n)` for n from 0 to m, so you need to sum those complexities up. What's the specific problem you're having? – Paul Hankin Jul 17 '20 at 12:11
  • You don't count the `printf` because it's just a constant factor. The Landau notation is defined such that the given function, multiplied with a constant factor and a constant offset, must be from a given `n` onwards always bigger than the actual growth. – Ext3h Jul 17 '20 at 12:11
  • the condition that the time calculation for printf() is ignored worries me. If it is ignored then the big-o would be just O(n). Isn't it? – Lee Jul 17 '20 at 12:13
  • Unrelated: `fib_iter(1)` returns 0. Shouldn't it return 1? – Ian Abbott Jul 17 '20 at 12:14
  • @pmg O(mn) where n is increasing from 0 to m is O(m^2). The total number of iterations is approximately m^2/2 plus some linear and constant terms that can be ignored. (Think: sum of integers 1 to N is (N^2 - N)/2, and this is in the same ballpark.) – Ian Abbott Jul 17 '20 at 12:29
  • but the condition says ignore the time complexity for printf(). Shouldn't time complexity for fib_iter(i) in printf() be ignored as well then? – Lee Jul 17 '20 at 12:34

1 Answers1

0

Try this:

int fib_iter(int n)
{
   int counter = 0;   // obs

   if(n == 0) return 0;
   if(n == 1) return 0;
 
   int pp = 0;
   int p = 1;
   int result = 0;

   for(int i = 2; i <= n; i++)
   {
      result = p + pp;
      pp = p;
      p = result;

      ++counter;   // obs
   }

   printf ("For n=%d counter is %d\n", n, counter);  // obs

   return result;
}

Now run with inputs as 16, 32, 64, ... and observe the counter.

Result:

For n=16 counter is 15
For n=32 counter is 31
For n=64 counter is 63

From this you can se that doubling the input value also doubles the number of loops. Consequently the complexity for the function is O(n).

For the main loop you call the function with values from 0 to m. An approximation of the number of loops in the function will be:

0 + 1 + 2 + 3 + ..... + m  =  (m + 1) * m / 2  =  (m^2 + m) / 2

When looking at complexity you only care about the most dominating part. Here that is m^2. Therefore you just "throw away" the + m part and /2 part.

So the complexity of the whole program is:

O(m^2)

OT: For large values of m you will get signed integer overflow. That is undefined behavior. If you switch to a unsigned integer type, overflow will not be undefined behavior (but the result will still be wrong).

Support Ukraine
  • 42,271
  • 4
  • 38
  • 63
  • I admire your effort but this is not the kind of solution I want. Your answer only returns time complexity of fib function. time complexity of the whole program with the condition given above. – Lee Jul 17 '20 at 12:19
  • @Lee Updated to cover the whole program – Support Ukraine Jul 17 '20 at 12:30
  • Well you have the answer correctly disregarding the conditions when it comes to solving the Big-O for the coded part. But the printf("fib(%d) = %d\n", i, fib_iter(i)); in for loop could be ignored totally according to the condition. Isn't it? – Lee Jul 17 '20 at 12:37
  • 1
    @Lee well... if you don't have the printf statement, you don't call the function! But if you just call the function in the loop (without printing the result), the complexity is just the same. It makes no difference whether or not you print the result. The reason for that is that printf is O(1) – Support Ukraine Jul 17 '20 at 12:38
  • Yeah, that was the point I was stuck on. Then O(n) as a result? – Lee Jul 17 '20 at 12:42
  • @Lee The `fib_iter` function is O(n). The whole program is O(m^2). – Support Ukraine Jul 17 '20 at 12:43