What is the time O-complexity of this code?

Question

I'm having a discussion with some other students from my program about what the O-complexity (regarding time) of this code would be:

public static void drawTriangle(int sizeOfTriangle) {
    for (int i = 0; i < sizeOfTriangle; i++) {
        for (int j = 0; j <= i; j++) {
            System.out.print("*");
        }
        System.out.println();
    }
}

They think it should be O(n^2) because of the nested for-loop and apparently that's also what the teaching assistant told them. However, I believe that it is O(n!) because the instruction System.out.print("*") is only ran exactly n! and not n^2 times. Can anybody please explain what the solution is and why? It would be very appreciated.

Edit: Sorry guys, I had a total brainfart where I thought n! = 1 + 2 + ... n and for some reason nobody pointed that out to me. I understand my mistake now ^^"

How do you compute that ```*``` is being printed ```n!``` times? — ksohan, Feb 15 '22 at 18:15
O(n!) is much bigger than O(n^2). The complexity is O((n^2)/2), but the constant 1/2 is ignored in O() calculations. It's not at all clear why you think it's O(n!). — Jim Garrison, Feb 15 '22 at 18:15
There is an easy way to make sure it certainly is not n!, try it with n = 100 and see if the program finishes. If it were n! you would be sitting there for enternity. Do you know what n! actually means? — luk2302, Feb 15 '22 at 18:22

score 3 · Answer 1 · answered Feb 15 '22 at 18:21

n! = 1 * 2 * 3 * 4 * ... * n

And in the nested loop you are printing:

*
**
***
****
*****

which is not n! but

1 + 2 + 3 + 4 + .... + n = (n * (n + 1))/2 = (n^2 + n)/2 where n/2 can be ignored and from n^2 * 1/2 1/2 can be ignored also.

So the complexity is O(n^2).

score 1 · Answer 2 · edited Feb 15 '22 at 18:28

It`s be n^2. Every include "for" cycle add n^+1.

for (int i = 0; i < 10; i++) {                //  n^1
   System.out.print("*");                //10
} 

for (int i = 0; i < sizeOfTriangle; i++) {    //n^2
   for (int j = 0; j < i; j++) {
      System.out.print("*");            //10*10
   }
   System.out.println();
}
for (int i = 0; i < 10; i++) {                //n^3
   for (int j = 0; j < i; j++) {
      for (int g = 0; g < i; g++) {
         System.out.print("*");               //10*10*10
      }
      System.out.println();
   }
}

What is the time O-complexity of this code?

2 Answers2