CODEWITHSUNDEEP
time-complexitycomplexity-theory
Mateusz
Mateusz

Reputation: 624

What is the complexity of this function with nested loops?

What is the complexity of this code?

public class test5{
public static void main(String[] args) {
   int n = Integer.parseInt(args[0]);
   for (int i = 1; i<=n; i++) {
      for (int j = 1; j<=i; j++) {
         System.out.print ("*");
      }
   System.out.println();
   }

  for (int i = n; i>=1; i--) {
      for (int j = 1; j<=i; j++) {
         System.out.print ("*");
      }
   System.out.println();
   }
}

}

My assumption is that it will take O(n^2) operations because n*(n/2) + n*(n/2). Am I right?

Upvotes: 0

Views: 66

Answers (1)

dfrib
dfrib

Reputation: 73206

You are correct, a tight upper asymptotic bound for both the first and second nested loop blocks—say T_A(n) and T_B(n), respectively—is O(n^2), and hence the function as a whole runs as O(n^2), asymptotically.

You can analyze this in detail using Sigma notation to count the number of basic operations in the inner loop blocks for each of the nested loop blocks T_A(n) and T_B(n):

enter image description here

Where we've treated the System.out.print ("*"); operation as basic operation.

Upvotes: 1

Related Questions