Consider the following pseudo‑code that processes an array $A[1\ldots n]$ of integers, where $n$ is even:

```
count = 0
for i = 1 to n:
if A[i] is even:
for j = i+1 to n:
count = count + 1
```

Assume exactly half of the elements are even and they occupy the first $n/2$ positions of the array (i.e., $A[1]$ to $A[n/2]$ are even). Express, as a simplified function of $n$, the total number of times the statement `count = count + 1` is executed. Then state the algorithm's time‑complexity using Big‑O notation.

Question

Consider the following pseudo‑code that processes an array $A[1\ldots n]$ of integers, where $n$ is even:

```
count = 0
for i = 1 to n:
    if A[i] is even:
        for j = i+1 to n:
            count = count + 1
```

Assume exactly half of the elements are even and they occupy the first $n/2$ positions of the array (i.e., $A[1]$ to $A[n/2]$ are even). Express, as a simplified function of $n$, the total number of times the statement `count = count + 1` is executed. Then state the algorithm's time‑complexity using Big‑O notation.

Accepted Answer

(\frac{3n^{2}}{8} - \frac{n}{4}), O(n^{2})

Gce Model Questions Vol1 2017 Computer Studies Question 8

Answer Options

About This Question

Master the Exam!