Consider the following pseudo‑code:\n\n``\ninteger n = input positive integer\ninteger count = 0\nfor i = 1 to n do\n for j = i to n do\n if (i + j) mod 3 = 0 then\n count = count + 1\n end if\n end for\nend for\noutput count\n```\n\n(a) What is the output when $n = 6$?\n(b) Derive a formula for $count$ as a function of $n$.\n(c) State the time‑complexity of the algorithm in Big‑O notation.\n(d) Propose an algorithm that computes the same $count$ in $O(n)$ time.

Question

Consider the following pseudo‑code:\n\n``\ninteger n = input positive integer\ninteger count = 0\nfor i = 1 to n do\n    for j = i to n do\n        if (i + j) mod 3 = 0 then\n            count = count + 1\n        end if\n    end for\nend for\noutput count\n```\n\n(a) What is the output when $n = 6$?\n(b) Derive a formula for $count$ as a function of $n$.\n(c) State the time‑complexity of the algorithm in Big‑O notation.\n(d) Propose an algorithm that computes the same $count$ in $O(n)$ time.

Accepted Answer

7; count = c0*(c0+1)/2 + c1*c2; O(n^2); O(1) algorithm using residue counts

City Guilds Model Questions Vol1 2017 Information Technology Question 39

Answer Options

About This Question

Master the Exam!