Comparison of time complexity

Question

I got those two algorithms with two for loops each - the first algorithm has in my opinion a quadratic running time. Does the second algorithm have the same running time - O(n^2)?

Algorithm 1:

for (int i = 1..n) { 
     for (int j = 1..n) {
          // sort m[i, j]
     } 
}

Algorithm 2:

for (int i = 1..n) { 
     for (int j = i..n) {
          // sort m[i, j]
     } 
}

I checked previous similar posts (Big O notation) but couldn't find anything to solve my problem - if you do so, please point me in the right direction.

Thanks!

Leandro Caniglia · Accepted Answer · 2019-02-08 02:22:44Z

2

Let's analyze Algorithm 2, the other one is similar.

Let's first agree in that sort m[i, j] is O((j-i)lg(j-i)).

Alg 2  = O(sum_{i=1}^n sum_{j=i}^n (j-i)lg(j-i))
      <= O(sum_{i=1}^n sum_{j=i}^n (n-i)lg(n-i))
      <= O(sum_{i=1}^n (n-i)^2 lg(n-i))
       = O(sum_{i=1}^n i^2 lg(i))
      <= O(sum_{i=1}^n i^2 lg(n))
       = O(n^3 lg(n))

On the other hand

Alg 2  = O(sum_{i=1}^n sum_{j=i}^n (j-i)lg(j-i))                      ; take 1/2 of terms
      >= O(sum_{i=n/2}^n sum_{j=(i+n)/2}^n (j-i) lg(j-i))
      >= O(sum_{i=n/2}^n sum_{j=(i+n)/2}^n (n-i)/2 lg((n-i)/2)))      ; because j>=(i+n)/2
      >= O(sum_{i=n/2}^n ((n-i)/2)^2 lg((n-i)/2)))
      >= O(sum_{i=n/2}^{(n+n/2)/2} ((n-i)/2)^2 lg((n-i)/2)))          ; 1/2 of terms
      >= O(sum_{i=n/2}^{3n/4} (n/8)^2 lg(n/8))                        ; -i >= -3n/4
       = O(n^3 lg(n))

answered Feb 8, 2019 at 2:22

Leandro Caniglia

14.9k4 gold badges33 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user10826235 Over a year ago

Thanksfor your answer. So in your opinion it would be both times O(n³)?

Collectives™ on Stack Overflow

Comparison of time complexity

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related