Reference no: EM13669450

1) For each of the following blocks, select a big-Theta notation from among Θ(1), Θ(log n),Θ(n), Θ(n log n), Θ(n2), Θ(n3), Θ(2n) and Θ(n!) for the number of times the statement x := x + 1 is executed. In each case justify your answer.
(a) for i = 1 to n
for j := 1 to i
for k := 1 to j
x := x+1

(b) i := n
while (i ≥ 1)
begin
x := x+1
i = i/2
end

(c) j := n
while (j ≥ 1)
begin
for i := 1 to j
x := x+1
j = j/3
end

(d) i := n
while (i ≥ 1)
begin
for j := 1 to n
x := x+1
i = i/2
end