CODEWITHSUNDEEP
javaalgorithmtime-complexitybig-o
Tom
Tom

Reputation: 3

Big O notation (Algorithms)

Hi I am new to Big O Notation and having trouble specifying big O for the following if someone could kindly explain to me how to work it out please

int sum=1;
for(int count=n; count>0; count/=2) {
    sum=sum*count;
}

Upvotes: 1

Views: 177

Answers (3)

OmG
OmG

Reputation: 18838

As each time count is divided by 2, it will be Theta(log n) (from n to 0). Hence, it is in O(log(n)) as well.

Upvotes: 3

Giorgi Tsiklauri
Giorgi Tsiklauri

Reputation: 11110

count gets halved per each iteration. If n = 64:

step1 => count = 64
step2 => count = 32
step3 => count = 16
...

Therefore, its worst case scenario has a O(log n) time complexity.

In this case, however, your loop's body has a constant number of operations, therefore, best, worst, and average case scenarios are same, and:

Ω(log n) = Θ(log n) = O(log n)

Upvotes: 1

Aashrut Vaghani
Aashrut Vaghani

Reputation: 62

In the first line, the code will run once, so for it, the complexity is O(1). In second line a for loop will run until count > 0 and we can see that it will be divided by 2 every time loop runs and so it will just go on continuously infinite times. So basically, you cannot apply Big O notation on an infinite loop. And so also you cannot apply big O to the code inside the loop as well. So if there exist any O(infinite) then it could be an answer, but it won't exist. So you cannot define time complexity until and unless n<=0. if n<=0 then only the code will run once and complexity will be O(1).

Upvotes: 1

Related Questions