Search code examples
data-structurestime-complexitybig-ocomplexity-theory

Big O notation for n/2 in while-loop

I'm new to data structure and the likes of it.

I would like to ask a question, how do we determine the Big-O notation value of this process:

while(n%2==0){
   console.log(2);
   n=n/2;
}

What is the Big-O notation? Thanks before.

Solution

  • If n odd then the loop is not executed. If n is even then it takes log2n (i.e., log of base 2) iterations until the loop stops. It is log2n because n gets decrement to half each loop iterations (i.e., n=n/2;).

    Assuming that console.log(2); takes c time the overall complexity would be O(logn).