Problem 1: Assume that n is a positive integer. For each of the following algorithm segments, how many times will the innermost loop be iterated when the algorithm segment is implemented and run?

1) for k := 1 to n

for j := 1 to k

[Statements in the body of the inner loop, none containing branching statements that lead outside the loop]

next j

next k

2) for k := 1 to n

for j := 1 to k

for i := 1 to j

[Statements in the body of the inner loop, none containing branching statements that lead outside the loop]

next i

next j

next k

3) for k := 1 to n-1

for j := 1 to k+1

[Statements in the body of the inner loop, none containing branching statements that lead outside the loop]

next j

next k