0

I'm recently in to the algorithms and I'm having trouble finding the time complexity(Big-Oh notation) of the following algorithm:

for(int i=0;i<=n;i++){
for(int j=i;j<=n;j=j/2){
for(int k=0;k<=n;k=k*2){
//set of statements
}}}

Can anyone help me to determine the complexity of the following algorithm. I found the inner loop(k-loop) to be independent and it's complexity is (log n).when finding the i,j loop it sort of put me in confusion that what sequence it will become when j=j/2?

Mitul
  • 59
  • 5
  • You can start here: [What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?](https://stackoverflow.com/questions/362059/what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop) (Why not share what you already did to come to an answer?) – Luuk Apr 09 '22 at 09:36
  • @Luuk yeah I know about the simple dependent loops iterations(usually have arithmetic sequence) , the part which is confusing me is j=j/2.. – Mitul Apr 09 '22 at 09:39
  • 1
    Maybe use [edit], and improve your question ? – Luuk Apr 09 '22 at 09:41
  • These videos will be helpful, if you’re new to Time Complexity Analysis! [[1](https://youtu.be/9TlHvipP5yA)] [[2](https://youtu.be/9SgLBjXqwd4)] [[3](https://youtu.be/p1EnSvS3urU)] – Deepthi Tabitha Bennet Apr 09 '22 at 16:03

1 Answers1

0

Worst case for any positive integer - this will run infinitely as the innermost loop i.e. K-loop, will never terminate as it is initialized with 0 and updated to 0 all the time(k=k*2).

babybob
  • 444
  • 6
  • 22