Consider the following pseudocode: for i 2 {1; 2; : : : ; 10} do statementA for

Question

Consider the following pseudocode:
for i 2 {1; 2; : : : ; 10}
do
statementA

for j 2 {1; 2; : : : ; n}
do
statementB
end
for k 2 {1; 2; 3; 4} do
for l 2 {1; 2; : : : ; n} do
statementC
end
end
end

(a) Which statement will be executed the most number of times?
(b) Suppose that statement A requires 3n operations, B requires n^2 operations, and
C requires 30 operations. How many operations does this pseudocode require in
total?
(c) Show that the number of operations required in part (b) is in big-theta(n^3).

Simple And Correct Answer Will Earn You A Lifesaver Rating

Explanation / Answer

a) statementC - executed 10*4*n = 40n times b) Total number of times A is executed = 10 Total number of times B is executed = 10n Total number of times C is executed = 40n Total no. of operations = 10*3n + 10n*n2 + 40n*30 = 10n3 + 1230n c) 10n3 + 1230n < 11n3 for all n>36 10n3 + 1230n > 10n3 for all n>0 Hence, it is in ? (n3)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---