What is the time O-complexity of this code? [duplicate]

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 ^^"

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
– Jim Garrison, Commented Feb 15, 2022 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
– luk2302, Commented Feb 15, 2022 at 18:22

ksohan · Accepted Answer · 2022-02-15 18:21:26Z

3

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).

answered Feb 15, 2022 at 18:21

ksohan

1,1992 gold badges10 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Gray · Accepted Answer · 2022-02-15 18:28:15Z

1

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();
   }
}

edited Feb 15, 2022 at 18:28

Gray

117k24 gold badges305 silver badges360 bronze badges

answered Feb 15, 2022 at 18:25

Oleg

797 bronze badges

Collectives™ on Stack Overflow

What is the time O-complexity of this code? [duplicate]

2 Answers 2

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Linked

Related