-2

What is the time complexity for this? And what's the Big-O?

int sum = 0;
    
for (int i = 0; i<= 20; i+=2)
     for (int j = 0; j<= i; j++)
          sum+= 2i * j ;
System.out.println (sum);
System.out.ptintln(“I = ” + i + “ J = ” + j);
John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Rim
  • 29
  • 1
  • 6
  • Duplicate [Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities](https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities) – Lunatic Mar 05 '22 at 06:49

2 Answers2

2

Since nothing depends on any input and the number of iterations is always fixed, this has constant-time complexity or O(1). Asymptotic runtime complexity is always a property of a function describing how the number of operations change in relation to the input size.

There is no input and the function always takes the same time to execute, hence O(1).

  • Function performs the same operations regardless of its input: O(1)
  • Function runs twice as long when input doubles: O(n)
  • Function runs 4 times slower when input doubles: O(n²)
  • Function performs more operations, but less than you would expect from N: usually O(log n)
knittl
  • 246,190
  • 53
  • 318
  • 364
0

Since the main loop's iterations does not increase/decrease drastically with change in input, the code is O(N).

You can give whatever limit you want to the I<=20 iterator, and the iterations will grow linearly

Sriram Vinodh
  • 9
  • 1
  • 1
    If the outer loop is not dependent on the input and the inner loop is not (it isn't), then this has constant time complexity O(1) – knittl Mar 05 '22 at 06:44
  • And if `20` was replaced with a variable `N`, then the complexity would be `O(N^2)`. You can figure this out by working out the precise formula that relates `N` to the number of times that `sum+= 2i * j` is executes. – Stephen C Mar 05 '22 at 06:51