Big-O Efficiency measurement

Question

I'm a java student who wants to get a better understanding of the big-O efficiency.

For this problem, it is assumed that doIt() has an efficiency of O(n).

 j=n;

 while (j>0) {

    doIt();

    j = j / 2;

}

i = 1;

while (i < n) {

i = i * 2;

doIt();

}

What would be the big o efficiency of this algorithm, and why would it be that efficiency (such as O(n logn), O(n^2), O(n^2 logn), etc.).

score 1 · Answer 1 · answered Jan 05 '18 at 20:29

1

First loop is O(nlog(n)) and the second on is the same. Hence the total complexity is O(nlog(n)).

Also, instead of big-O can big-\Theta notation too.

For the first loop, number of iterations is the number of dividing n by 2 which is log(n) and the second loop can be explained the same (by multiplication instead of division).

answered Jan 05 '18 at 20:29

OmG

18,337
10
57
90

i see, thanks for the clarification. That makes much more sense now. – slasdxyz Jan 05 '18 at 20:35

score 1 · Answer 2 · answered Jan 05 '18 at 20:35

Due to the halving, the first loop will execute log(n) times. The second loop will also execute log(n) times due to the doubling.

This means that doIt() will be called log(n) times per loop, yielding a total execution time of O(nlog(n)+nlog(n)), or O(2nlog(n)). As standard, drop the constant to yield your complexity of O(nlog(n))

Big-O Efficiency measurement

2 Answers2