Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

What is the Big O complexity of this algorithm

I can’t seem to figure out the time complexity for this algorithm. I know that the while loop will execute at O(log n) times because n keeps halving. But I’m not super sure how to represent the time complexity of the inner for loop.

while(n>0){
   for(int j = 0; j < n; j++){
        System.out.println("*");
   }
   n = n/2;
}

>Solution :

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

Each while loop divides n by 2.

Therefore, the first for loop would run n times, the second for loop would run n/2 times, the third for loop would run n/4 times, and so on.

If we set n to an arbitrary large value, then the complexity would be:

n + n/2 + n/4 + n/8 + n/16 + n/32 + ... = 2n

Of course, n is an integer, and programmatically, the division would result in 0 after enough repetitions.

Therefore, the time-complexity of the algorithm would be O(2N) = O(N)

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading