is the time complexity of nested for-loops always of O(n^2)?-CodePudding

for (i = 1; i <= n; i  )
{
   for (j = n; j >= i; j--)

}

I'm struggling with this algorithm. I can't even know what time complexity of this algorithm is? I've checked using online software it shows me only o(n).

CodePudding user response：

First of all, the algorithm should be something like this:

for (i = 1; i <= n; i  )
   for (j = n; j >= i; j--)
     DoSomeWork(i, j); // <- Payload which is O(1)

To find out the time complexity, let's count how many times DoSomeWork will be executed:

 i :    j : executed, times 
----------------------------
 1 : 1..n : n
 2 : 2..n : n - 1
 3 : 3..n : n - 2
.. :  ...   ...  
 n : n..n : 1

So far so good, DoSomeWork will be executed

  n   n - 1   n - 2   ...   2   1 = (n   1) * n / 2

times; time complexity for your case is

O((n   1) * n / 2) = O((n   1) * n) = O(n * n)   O(n) = O(n * n)

Nested loops are not necessary have quadratic time complexity, e.g.

for (i = 1; i <= n; i  )
   for (j = n; j >= i; j /= 2) // note j /= 2, instead of j--
     DoSomeWork(i, j);

has O(n * log(n)) time complexity

CodePudding user response：

Think about this a little. How many times do we enter into the outer loop? It's n times, as you surely already know, since we have step1, ..., stepn, in total n steps.

So, we have

n * average(inner)

In the first step, the inner loop has n steps. Then it has n - 1 steps and so on, on the final step we have 1 step in the inner loop.

so, the inner loop has:

n, n-1, ..., 1 steps in the respective iterations.

Since addition is both commutative and associative, we have:

(n 1) (n - 1 2) ...

that is (n 1)/2 on average.

Since we worry about the scenario when n -> infinity, adding 1 to it or dividing it by 2 is less of a concern, so we roughly have n * n steps, hence it has a complexity of O(n * n), don't listen to the tool that says otherwise, unless you have some extra information about your algorithm to share with us.