Crowdly

Add to Chrome

Given the following algorithm, matching each statement to the correct sequence f...

✅ The verified answer to this question is available below. Our community-reviewed solutions help you understand the material better.

Given the following algorithm, matching each statement to the correct sequence for complexity analysis.

procedure bin_exp_mod(b, n, m): b, n and m are positive integers

1 x = 1

2 p = b mod m

3 while (n != 0) do

4 if (n mod 2 == 1)

5 x = (x * p) mod m

6 end of if

7 p = (p * p) mod m

8 n = n div 2

9 end of while

a return x

First, there is one operation in line 2.

Then, the pseudocode contains a single while loop.

So, there are at most $2 \lfloor \log_2 n \rfloor + 3$ 2 \lfloor \log_2 n \rfloor + 3 operations.

We consider "mod m" as the operation to be analyzed.

In each iteration of the while loop, there are two operations in the worst case, and n is divided by 2.

Therefore, the total number of iterations is $\lfloor \log_2 n \rfloor + 1$ \lfloor \log_2 n \rfloor + 1

The complexity is $O(\log n)$ O(\log n)

Get Unlimited Answers To Exam Questions - Install Crowdly Extension Now!

Add to Chrome