Menu
I am trying to figure out the complexity of a for loop using Big O notation. I have done this before in my other classes, but this one is more rigorous than the others because it is on the actual algorithm. The code is as follows:
for(i=n ; i>1 ; i/=2) //for any size n
{
for(j = 1; j < i; j++)
{
x+=a
}
}
I have arrived that the first loop is of O(log_2(n)). As for the second loop I am a little lost! Thank you for the help in the analysis.
290
Two nested for loops: O(n²)
As the nested loops always run to completion and there is a constant amount of code within the inner loop, the time complexity can be determined by taking the sum of the number of inner loop iterations in the worst case.
"Are nested for-loops always O(n^2)?" To your other question, the answer is no. They aren't always O(n^2) . You can easily create a situation where one of the loops affects the iterations of the other, yielding a different complexity.
Putting all together. Continuing on the challenge to reduce the iterations on our algorithm, we have to perform the following steps: build the "index" with the information to be accessed later. iterate over the loop and fetch the additional information from the previously created "index"
To formally solve the your algorithm's time complexity, you may use the following steps with Sigma notation:
Also, take a look a the last slide of this very interesting document by Dr. Jauhar.
60
The overall number of iterations of inner loop is n + n/2 + n/4 + ... + 1 which is approximately 2n. So the complexity is O(n).
3
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
