time complexity of while loop in java

Question

Although I have used only one loop, I don't think the time complexity of my code is O(n). Could anyone please explain me the time complexity of the code below.

public class PatternPyramid {

    public static void main(String[] args) {

        int rows = 15;
        int i = 0;
        int j = 0;
        int k = rows - 1;

        while (i < rows) {

            if (j < k) {
                System.out.print(" ");
                j++;
            } else if (j < rows) {
                j++;
                System.out.print("* ");
            } else {
                j = 0;
                i++;
                k--;
                System.out.println();
            }
        }
    }
}

Aside from main question, those `continue` statements are redundant as they are always last instructions loop can invoke in that scenarios. — Pshemo, Jul 25 '20 at 18:56
@Pshemo thanks for your correction. I have edited my question. Now can you please explain me the time complexity of this code? — Mulkraj Singh, Jul 25 '20 at 19:06

score 1 · Accepted Answer · answered Jul 25 '20 at 19:18

1

The time complexity is O(n²), where n is the number of rows.

It requires n iterations to print each row of n characters. Furthermore, it requires n iterations to print each of the new lines.

Ergo, the time complexity is:

O(n * n + n)
= O(n² + n)
= O(n²)

answered Jul 25 '20 at 19:18

Unmitigated

76,500
11
62
80

thankyou. can you suggest way to decrease time complexity of this code? – Mulkraj Singh Jul 25 '20 at 20:51
@mulkraj I don't think there's anything wrong with its current time complexity. It is fast enough even for 1000 rows. – Unmitigated Jul 25 '20 at 20:52
thank you. Actually I wrote same code in python and i think that i reduced time complexity noticeably. – Mulkraj Singh Jul 28 '20 at 19:09

score 0 · Answer 2 · answered Jul 25 '20 at 19:23

0

for (int i=0; i<rows; i++) {
    for(int j=i; j<rows;j++)
        System.out.print(" ");
    
    for(int k=0; k<=i; k++)
        System.out.print("* ");
                
    System.out.println();
}

Your code could be transformed into for loops like this, as it can be seen that outer loop run O(rows) times, and the loop for spaces runs rows-i times for each iteration whereas loop for asterisks run i times. Combining them would result in the inner loops running rows times.

Thus total time complexity would be O(rows^2)

answered Jul 25 '20 at 19:23

Osama A.Rehman

912
1
6
12

how can we reduce the time complexity further? Any suggestions? – Mulkraj Singh Jul 25 '20 at 20:52
@mulkraj I think its the best time complexity you could have, because for any rows/input, you have to print rows^2 amount of spaces and asterisks. – Osama A.Rehman Jul 26 '20 at 06:02
1

@Osama_Abdul_Rehman thank you. – Mulkraj Singh Jul 28 '20 at 19:10

time complexity of while loop in java

2 Answers2