The following pseudo‑code is executed with a positive integer $n$:

```
count = 0
for i = 1 to n:
for j = 1 to floor(n / i):
count = count + 1
```

(a) Express the total number of executions of the inner statement as a summation and state the asymptotic time‑complexity of the algorithm in Big‑O notation.
(b) Using the summation, find the exact number of executions when $n = 100$.

Question

The following pseudo‑code is executed with a positive integer $n$:

```
count = 0
for i = 1 to n:
    for j = 1 to floor(n / i):
        count = count + 1
```

(a) Express the total number of executions of the inner statement as a summation and state the asymptotic time‑complexity of the algorithm in Big‑O notation.
(b) Using the summation, find the exact number of executions when $n = 100$.

Accepted Answer

Total executions = $\sum_{i=1}^{n} \left\lfloor \frac{n}{i} \right\rfloor$ (O(n log n)); for n=100 the total is 482.

Gce Model Questions Vol1 2024 Computer Studies Question 35

Answer Options

About This Question

Master the Exam!