0

Say I have a function

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            System.out.println("Operation " + counter);
            counter++;
        }
    }
}

Here complexity is n^3 and print operation runs n^3 times.

Suppose I have a program like fibanocci sequence:

public  static  int method6(int n) {
    // complexity O(2^n)
    if (n <= 1)
        {
        recursiveOperationCount += 1;
        System.out.println("Operation1 " + recursiveOperationCount);
            return n;
        }
    else {
        recursiveOperationCount += 1;
        System.out.println("Operation1 " + recursiveOperationCount);
        return method6(n - 1) + method6(n - 2);
    }
}

I know that the complexity is 2^n but the print operation happens 176 times for n = 10. Should the print have been printed 2^10 = 1024 times ?

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Leo Baby Jacob
  • 87
  • 8
  • 1
    No, that's not what time complexity means. It's not a count of how many operations the program does; it's a description of how the time (or the number of operations) grows as the input amount grows. – khelwood Oct 03 '21 at 22:38
  • I get it, I totally understand that complexity is as per the n i.e linear polynomial logarithmic etc. But in the last example the one with method6 it is basically recursive fibanocci. Now even though print happens 16 times for n=10 the code still has 2^n complexity right – Leo Baby Jacob Oct 03 '21 at 22:46
  • The time complexity is not `O(2^n)`. Its approximate *upper bound* may be `O(2^n)`, but your example shows it's actually less for this concrete case. – Bohemian Oct 03 '21 at 22:47
  • It can be approximated to 2^n right – Leo Baby Jacob Oct 03 '21 at 22:53
  • `O(2^n)` is a *very* rough approximation of the upper bound - see [here](https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence) – meowgoesthedog Oct 04 '21 at 09:28

0 Answers0