Consider the following loop construct: X := 1 repeat Y := N while Y > 0 do . . .

Question

Consider the following loop construct:

X := 1

repeat

Y := N

while Y > 0 do

. . . // something (the ellipsis)

Y := Y - 1

endwhile

X := X + X

until X > N * N

Categorize its efficiency in terms of the variable N using big-O notation. Also, assume that the statements represented by the ellipsis require four main memory accesses with each access requiring 1 microsecond, and two disk file accesses with each requiring 1 millisecond. Express in milliseconds the amount of time this construct would require to execute if N = 1000.

Explanation / Answer

it takes 4 memory operations of 1 ms each plus 2 disk operations of 1 ms each for one iteration:
4 * 1 + 2 * 1 = 6

So, 6 ms total per iteration. Now, just multiply 6 by how many iterations you require for n = 1000. Since you know the complexity is O(n^3)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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