CODEWITHSUNDEEP
runtimecomplexity-theory
gadona91
gadona91

Reputation: 1

runtime of a block code

Can someone please explain to me why this code has a runtime complexity T(n) of 2lgn+2. I thought it should be lgn+2. 

public static reduce(int n){
 int result = 0;
 while (n >1){
   n = n/2;
   result = result +1;
 }
 return result;
}

Upvotes: 0

Views: 31

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55619

Presumably each line is assumed to take 1 unit of time (not including the n > 1 check).

So int result = 0;, n = n/2;, result = result +1; and return result; each classify as taking 1 unit of time.

2 comes from int result = 0; and return result; each being executed once.

2 log2n comes from n = n/2; and result = result +1; each being executed log2n times.

Note:

n > 1 could also classify as a unit of time resulting in 3 log2n + 2.

n = n/2; and result = result +1; could each classify as taking 2 units of time resulting in (with the above) 5 log2n + 2.

It's all very subjective.

The only across the board agreement would be c log2n + d for some c and d.

Upvotes: 1

Related Questions