0

How to find time complexity of nested loops? also, how to find time complexity of a program consisting of more than one functions?

Basically, I'm confused when to add/multiply the time complexities.

#include <stdio.h>

long pascal(int, int);

int main()
{
   int n,m,k,j;

   printf ("Enter the height for Pascal's Triangle: ");
   scanf("%d", &n);

   for(k = 0; k<n; k++)
   {
      for(j = 0; j < n-k; j++)
        {
          printf(" ");
        }
      for(m = 0; m <= k; m++)
        {
          long f = pascal(k, m);
          printf("%ld ", f);
        }
        printf("\n");
    }
    return 0;
}

long pascal(int n, int i)
{
    if(n == i || i == 0)
        return 1;
    else
        return pascal(n-1, i) + pascal(n-1, i-1);
}

This was the code I used for printing Pascal's triangle. How to find its time complexity?

Hulk
  • 6,399
  • 1
  • 30
  • 52
A4n
  • 21
  • 5
  • Time complexity is the number of "steps" the program is making (up to a constant factor/offset). So you add the "complexities" when the steps are added, and you multiply them when they are multiplied. When you have a nested loop, obviously the number of steps in the inner loop is multiplied by the times the outer loop is running. Unless these numbers are not constant and form some kind of series. – Eugene Sh. Aug 12 '20 at 15:18
  • Related: https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop – Hulk Aug 12 '20 at 15:18
  • Does this answer your question: https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm?noredirect=1&lq=1 ? – Hulk Aug 12 '20 at 15:22
  • In your inner loop, you first do `n-k` steps, and then you do `k` steps - together that is `n` steps on first glance, and as you repeat this n times, this is O(N²) iterations. However, you then invoke a recursive function, which adds complexity. – Hulk Aug 12 '20 at 15:34
  • Related: https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation – Hulk Aug 12 '20 at 15:37
  • Beware that big factors like n^2 wash out lesser ones except sometimes as multipliers like N^2 log N graphs very close to N^2. – David G. Pickett Aug 12 '20 at 16:04
  • `pascal` recurses 2 times with linear steps so is O(N)*O(N) (i.e. O(N^2)). The inner and outer loops of `main` from which `pascal` is called each contribute a multiplier of O(N), so the total is O(N^4). (The other inner loop that prints the spaces is insignificant because the total complexity of that part is O(N^2).) – Ian Abbott Aug 12 '20 at 17:01

1 Answers1

0
  • Your 1st loop - for(k = 0; k<n; k++) runs Θ(n).
  • Your 2nd loop - for(j = 0; j < n-k; j++) runs as an arithmetic progression so it Θ(n^2).
  • Your 3rd loop runs as 2nd loop, so Θ(n^2).
  • Your pascal function runs O(2^n) because it is recursive with 2 parts: pascal(n-1, i) + pascal(n-1, i-1); You can see in this link the full explanation: https://stackoverflow.com/a/360773/13292734

In conclusion:

  • Without the pascal function, the time complexity is Θ(n^2).
  • But the longest time that occurs is in the function pascal, which the time complexity is O(2^n/sqrt(n)). You can see here why is O(2^n/sqrt(n)) and not O(2^n): https://stackoverflow.com/a/26229383/13292734
  • So the time complexity is: O(n^2)*(2^n/sqrt(n)). Or you can say: O(n^2)*(2^n) it's correct too.
gera verbun
  • 285
  • 3
  • 6