Определить временную сложность арифметического c прогрессии

Question

Я новичок в анализе сложности времени. Кто-нибудь может мне помочь с временной сложностью приведенного ниже алгоритма?

public void test(int n)
{
  for(int i=1;i<=n;i=i+2)
    {
     for(int j=1;j<=i;j++)
     {}
    }
}

external l oop будет выполняться n / 2 раза. Внутренний l oop будет работать (1 + 3 + 5 + 7 + 9 ... n) раз. какова будет временная сложность внутреннего l oop и как мы можем вычислить сумму таких арифмитов c прогрессии?

Answer 1

Предположим, что n нечетно. Тогда n = 2k + 1 для некоторого k. Теперь

  1 + 3 + … + n
= 1 + 3 + … + 2k+1
= (1 + 3 + … + 2k + 1) + (1 + 1 + … + 1) - (1 + 1 + … + 1)
= (1 + 1) + (3 + 1) + … + (2k + 1 + 1) - (1 + 1 + … + 1)
= 2 + 4 + … + 2k+2 - (1 + 1 + … + 1)
= 2(1 + 2 + … + k+1) - (1 + 1 + … + 1)
= 2(k+1)(k+2)/2 - (k+1)
= k^2 + 3k + 2 - k - 1
= k^2 + 2k + 1
= (k+1)^2
= (n+1)^2/4

Мы можем протестировать несколько терминов ...

n    f(n)    Series Sum
1    1       1 = 1
3    4       1 + 3 = 4
5    9       1 + 3 + 5 = 9
7    16      1 + 4 + 5 + 7 = 16

Похоже, все получилось.