S <--- 0
for i==1 to n do
for j==1 to i do
S <--- S+1
end for
end for
write(S)
I don't know how to come about resolving this problem.
I tried calculating the complexity of the j loop but couldn't get a solution
Add a comment
|
1 Answer
The first loop has n steps, so it's of linear complexity. The nested loop's average formula will help you to understand this further.
First, it's of n steps. Then it's of n - 1 steps. Then it's of n - 2 steps. And it is decreasing until it is of a single step. So the average is of:
(1 + 2 + 3 + ... + n) / n
This is an arithmetic progression. You see that pairing the first with the last is n + 1, pairing the second with the penultimate is 2 + n - 1 = 1 + n, ... pairing the i'th element from the left with the i'th element from the right, you have i + n - i + 1 = n + 1. So, you have n / 2 pairs of n + 1, which therefore equals to n * (n + 1) / 2 and if we divide it with n in order to get the average, then we get n * (n + 1) / 2n = (n + 1) / 2, which is roughly half of your n, which is, if n -> infinity, then rendering the division by 2 irrelevant, so the complexity if quadratic, i.e., O(n^2). After this algorithm, you write the result, which is presumably irrelevant to the complexity.
2 Comments
David G
I'm not getting how you concluded that the complexity is quadratic by considering n as it approaches infinity. (n+1)/2 looks linear to me. There's no extra n term.
Lajos Arpad
@DavidG that (n+1)/2 is a nested loop of n, so you have n * (n + 1) / 2, as you have a loop with i and a loop with j inside of it.
