Question

Give the most compact theta notation for the number of times the statement
x = x + 1 is executed in the following pseudo-code:
for i = 1 to i = 3n − 1{
for j = 1 to j = n{
x = x + 1
}
}

Answer 1

Answer on Question #62637 – Math – Algorithms | Quantitative Methods

Question

Give the most compact theta notation for the number of times the statement $x = x + 1$ is executed in the following pseudo-code:

for $i = 1$ to $i = 3n - 1$ {

for $j = 1$ to $j = n$ {

$x = x + 1$

}

}

Solution

The inner loop with index $j$ performs the statement $x = x + 1$'s n times.

The loop with index $i$ performs the inner loop $(3n - 1)$ times.

Thus, both loops perform the statement $x = x + 1$'s $(3n - 1)$'s n times.

Here $(3n - 1)n = 3n^2 - n$ is a quadratic function, drop the factor 3 and the low-order term $-n$.

So the most compact theta notation for the number of times when the statement

$x = x + 1$'s is executed will be $\Theta(n^2)$.

Answer: $\Theta(n^2)$.

www.AssignmentExpert.com