Can someone sanity check me on this that the function is O(n^2)static void f(int n) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= i; j++)
System.out.print("*");
System.out.print("\n");
}
}
>>62041857
I'm not going to give you the answer, but you should plug in a number for n. Then count the number of times the for loops will be called. If the result is n^2, then it's O(n^2).
>>62041857
Just code it and see what happens
>>62041857
Yes. The inside loop will first run once, then twice, then thrice, etc. So the * gets printed
1 + 2 + 3 + ... + n
times. This formula is for the "nth Triangular Number" and it has a general formula of
1 + 2 + 3 + ... + n == n*(n+1)/2
Expanding the right hand side out gives (n^2)/2 + n/2 + 1/2, which is indeed O(n^2)