Питання | Сторінка 139658

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

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

We consider ∗* as the operation to be analyzed

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

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

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

The pseudocode contains a single while loop.

Переглянути це питання

Crowdly