Какова сложность этой функции с вложенными циклами?

Question

Какая сложность этого кода?

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

}

Мое предположение, что он будет принимать O (N^2) операции, так как п * (п/2) + п * (п/2). Я прав?

Answer 1

Вы правильно, плотно верхний асимптотическая граница для первого и второго вложенного цикла блоков, скажем T_A(n) и T_B(n), соответственно, является O(n^2), и, следовательно, функция в целом работает как O(n^2), асимптотически.

Вы можете проанализировать это в деталях, используя Sigma нотацию для подсчета количества основных операций в блоках внутренних петель для каждого из вложенных блоков цикла T_A(n) и T_B(n):

Где мы обрабатывали Операция System.out.print ("*"); как основная операция.