Question

Consider the following function f: int f(int n) { int s = 0; while(n > 1) { n = n/2; S++; } return
s; } What is the asymptotic complexity in terms of n? (Pick the smallest correct answer)​

Answer 1

Answer:  O(log n)

Given Algorithm:

int f(int n)

{

int s = 0;

while(n > 1)

{

n = n/2;

s++;

}

return s;

}

To find: (among the options given)

The asymptotic complexity in terms of n. (Pick the smallest correct answer)

A. O(n log n)

B. O(n)

C. O(√n)

D. O(log n)

E. O(n²)

Explanation:

The time complexity will be O(log n). This is because of the phenomenon by following which the algorithm is dividing the working area into half in every iteration.

So, the division into halves will create the Logarithmic Time Complexity and the running period of the algorithm will be directly proportional to the number of times the number 'n' gets halved (or divided by 2).

Therefore, O(log n) will be the asymptotic complexity of the given algorithm.

Learn more:

1. What is list comprehension python?

brainly.in/question/6964716

2. Noisy values are the values that are valid for the dataset, but are incorrectly recorded. Is it?

brainly.in/question/6658996