Determine the computational complexity of the following algorithm

Question

s = 0
for i = 1 to n3
for j = 1 to i do
s = s + 1

what is mean by computational complexity?

So, the actual question is "what is computational complexity"? — Benjamin W., Mar 25 '17 at 04:14
Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Paul Hankin, Mar 25 '17 at 14:23

score 1 · Answer 1 · answered Mar 25 '17 at 04:45

Let's assume each operation i in this code takes constant time c_i. Then the running time can be expressed by the sum c₁ + c₂ * n3 + c₃ * i * n3 + c₄ * i * n3. We consider constant coefficients as insignificant because they only contribute a constant value regardless of the input. This gives us Θ(1) + Θ(n3) + Θ(i * n3 + 1) + Θ(i * n3). So in this case the time complexity is Θ(n3!) which is to say this algorithm runs in factorial time.

score 0 · Answer 2 · answered Mar 25 '17 at 16:37

0

Just calculate some values (how many times s = s + 1 is executed for each iteration of i and sum up) and see what you get:

1 + 2 + 3 + ... + n = n * (n + 1) / 2 = n^2 / 2 + n / 2 => complexity O(n^2).

answered Mar 25 '17 at 16:37

maraca

8,468
3
23
45

Determine the computational complexity of the following algorithm

2 Answers2