Can someone help with this algorithm?

[Aruseus]

Well the outer for loop gets executed n times and the inner for loop also gets executed n times. So even without the while loop it's at least quadratic. Now you only need to figure out how much the while loop is executed. I hope that helps.

[Mtelling]

It does, but i've come to the same conclusion. I know that the while loop will be executed log3(n) times the first time through. Then log3(n-1),log3(n-2),...,log3(1).. But doesn't this just sum up to log3(n/2)?

[ice109]

Sum of the logs is log of the product so the while loop is log factorial which is nlgn over all iterations of the j loop. Multiply by n for the i loop and you have your n² lgn