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(b, n): b and n are positive integers

1 x = 1

2 p = b

3 while (n != 0) do

4 if (n mod 2 == 1)

5 x = x * p

6 end of if

7 p = p * p

8 n = n div 2

9 end of while

a return x

The pseudocode contains a single while loop.

Since nn is divided by 2 in each iteration, the total number of iterations is ⌊log2n⌋+1\lfloor \log_2 n \rfloor + 1

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

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

Therefore, there are at most 2⌊log2n⌋+22 \lfloor \log_2 n \rfloor + 2 operations.

We consider ∗* as the operation to be analyzed

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

Додати до Chrome