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?

steve
  • 19
  • 3
  • 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.. – steve 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

0 Answers0