Big inference analysis for an algorithm
Further down in my series of Big O questions that I cannot find an answer to
Let's take the following example
for(int i = 0; i < someNumber; i++)
{
for(int j = i; j < someNumber; j++)
{
DoSomething();
}
}
Will this still count as O (n ^ 2)? I'm only asking because I feel like it should be less than O (n ^ 2), as the inner loop runs less and less for each iteration i (as j starts getting closer and closer to someNumber).
thank
+3
source to share
1 answer
The outer loop is executed n times. The inner loop starts n times, but decreases with each iteration of the outer loop until the last iteration, where it is executed only once. The code inside the inner loop will work
n + (n-1) + ... + 2 + 1
time.
This can be simplified to n (n + 1) / 2 ( proof ), or n 2 /2 + n / 2, or, finally, (n 2 + n) / 2. Since the first term n 2 the algorithm is in O (n 2 ) ,.
+16
source to share