Crowdly

Додати до Chrome

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

✅ Перевірена відповідь на це питання доступна нижче. Наші рішення, перевірені спільнотою, допомагають краще зрозуміти матеріал.

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)

Отримайте необмежений доступ до відповідей на екзаменаційні питання - встановіть розширення Crowdly зараз!

Додати до Chrome