Есть один алгоритм. Нужно подсчитать количество арифметических операций ( умножений, делений и сложений) в алгоритме для n. Знаю что сложность будет кубическая , но точно какая подсчитать не смог.

Вот сам алгоритм:

Странно, что не получилось, ведь тут вроде не очень сложно.
Умножение: есть цикл по i, выполняющий n итераций, внутри него каждый раз происходит n-1 умножение (от 0 до i-1 и от i+1 до n-1), т.е. всего n(n-1).
Деление: на первой итерации (i=0) выполняется n-1 деление, на второй n-2, и т.д., на последней 0. Складываем все значения - получаем сумму арифметической прогрессии, и получаем всего n*(n-1)/2.
Со сложениями посложней, потому что не совсем понятно, что считать сложением  (ну всякие ++, или i+1)
Ну например, если считать только операции +=, то получится, столько же, сколько умножений.

Да не всё так просто получается как кажется на первый взгляд.
А вы разве не заметили что при 2-ом запуске k - ого цикла он имеет 3 уровень вложенности! А это означает что сложность алгоритма будет кубическая!  Вы не обратили внимание , что ещё имеется цикл j = i+1...n а уже в нем k-ый. Если считать что как вы написали то это получается общая сложность : (1.5n)^2+2.5n - а это квадратичная сложность получается. К тому же , даже если бы не было 3  - его уровня вложенности то умножений было бы не n(n-1) а  2n(n-1) - так как на каждой итерации выполнялось бы 2(n-1) умножений sum += A[k][i] * A[k][i] *A[k][k];

 

Vitaly333
Хе, да уж, я умудрился не заметить третий for ))
Меня колбасит после сдачи вычислительной математики, прошу извинить 

Если принять, что третий for выполняется всегда, можно посчитать верхнюю асимптотическую оценку сложности алгоритма

Подождите, а третий (по глубине вложенности) for - ведь количество итераций в нём никак не зависит от j.
Значит, при оценке кол-ва операций его можно рассматривать наравне с forами второго уровня, т.е. например:

Умножение: есть цикл по i, выполняющий n итераций, внутри него каждый раз происходит 2(i-1) умножение, и плюс 2(n-i-1)(i-1) умножение; вот нужно просуммировать такие величины, для этого можно попробовать выразить их рекуррентно...

Выполняется всегда кроме первой итерации (когда i = 0). Под верхней асимптотической оценкой сложности алгоритма вы понимаете только  умножения при n^3?



Просуммировать по i = от 0 до n-1?

Ага.
Или как раз эту сумму не получается посчитать?
Вообще, вот что имеем:
2(n-i-1)(i-1) = 2(n-2-(i-1))(i-1) = 2(n-2)(i-1) - 2(i-1)^2.
Т.е. получили сумму обычной арифметической прогрессии, и последовательности вида 1,4,9,16...; сумма для неё точно есть, я в книге какой-то видел, можно попробовать вывести самому или поискать в интернете.

Но это опять же получается квадратичная сложность...

Нет, это одно слагаемое порядка квадрата. А вся сумма, очевидно, получится порядка куба.
Я даже помню, что формула для суммы последовательности 1,4,9,16,... содержит три скобки-множителя.

Добавлено через 10 минут и 33 секунды
Вот, сам нашёл эту формулу 
Sn = 1/6 n (n+1) (2n+1)

Это сумма только операций умножения или вообще всех операций? Не могли бы вы подкинуть ссылку гду вы это нашли?

Это сумма для ряда 1+2^2+3^2+...+n^2.
Сумму для ряда 1+2+...+n, надеюсь, все знают )
Тогда мы в состоянии вычислить значение такой вещи:
СУММА 2(n-2)(i-1) - 2(i-1)^2 по i = 0..n-1

Ссылка на формулу для ряда, составленного из квадратов:
http://mathworld.wolfram.com/SquarePyramidalNumber.html