Hello guys Iam new to competitive programming and Big O notation I am still learning the basics.
So the algorithm for which the time complexity is to estimated is this
int a = 0;
for (i = 0; i < n; i++) //runs from i-n;
for (j = i; j < i * i; j++) // runs from i - i*i;
for (k = 0; k < j; k++) //runs from 0 - j;
a++;
I have commented the basic details that i have understood about the algorithm.
The outer loop clearly runs O(n) times and first inner loop runs from 'i' to 'i*i'
The second inner loop runs '0' to 'j'
I also know i have to apply the rule of products.
But I am unable to calculate the time complexity of the two inner loops relative to 'n'.
Please correct me if im wrong with my explination. And help me out with this problem
Thank you very much.
When you have multiple levels of for loops, analyze the complexity of each loop in isolation and then multiply them together.
In this example, the complexity of the first loop is O(n), like you said.
The complexity of the second loop is O(n^2) because in the worst case, the number of operations you have to perform is on the order of i*i which could be as big as n^2. It doesn't matter that it doesn't start at zero either because in an expression like O(n^2 - n), everything but the highest order term gets ignored.
The third loop also takes O(n^2) because in the worst case, you could have as many as j operations would again could be as big as n^2.
Lastly a++ happens in constant time. Multiply everything together and you have a complexity of O(n^5).
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments