Select a theta notation from among Theta(lg n), Theta(n), Theta(n lg n), Theta(n

Question

Select a theta notation from among Theta(lg n), Theta(n), Theta(n lg n), Theta(n^k), Theta(2^n), Theta(n!) for the number of times the statement x:=x+1 is executed in x:=0 for i:=1 to 2n for j:= 1 to 2i+1 x:=x+1 Solution. For each I = 1, 2, 3, ..., 2n the inside for loop is executed once which involves 2i + 1 executions of x:= x + 1. Hence the total number of executions of x:= x +1 is Sigma_i=1^2n (2i + 1) = Sigma_i=1^2n 2i + Sigma_i=1^2n 1 = 2 Sigma_i=1^2n i + 2n = 2(2n + 1)2n/2 + 2n = 4n^2 + 4n = theta(n^2)

Explanation / Answer

10)

Answer:

(n3) big-Theta notation for the number of times the statement x := x + 1 is executed because in given segment, mainly three operations are carried out each time, the k loop runs for j times, j loop runs for i times and i loop runs n times. Therefore the Running time of this function is (n3).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.