-4

I'm using #include <bits/stdc++.h> using namespace std; and so the sort() function would be nlogn.

for(int i=0;i<n;i++){
    statement;
}

for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
        statement;
    }
}

sort(arr,arr+n);
sort(arr2,arr2+n);

for(int i=0;i<n;i++){
    statement;
}

I'm not sure if the total time complexity is O((m * n)+nlogn+2n) or O((m * n)+2(nlogn)+2n)..

EL pasta
  • 15
  • 3
  • 2
    The two possibilities you've listed are the same time complexity. A constant coefficient on `n log n` doesn't change that. – Nathan Pierson Nov 12 '20 at 04:53
  • Can you give more information?? What does m means in this code. a constant, a variable or what else? – Phoenix Chao Nov 12 '20 at 05:01
  • Your two time complexities are equivalent to O(m*n + n log n). Constant coefficients don't matter and the n log n subsumes the n. – Anonymous1847 Nov 12 '20 at 05:06
  • Complexities are usually expressed in a much simpler notation. In any case, easiest way to find out is to try with different values of `m` and `n` and chart it. – tadman Nov 12 '20 at 05:22
  • You shouldn't use [`#include`](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) – Geno C Nov 12 '20 at 05:38

1 Answers1

0

You got it right anyway and I will explain. If you really calculate every line in your code, then you get: O(n) + O(nm) + O(nlogn) + O(nlogn) + O(n), which is in total: O( 2n + 2nlogn + nm). However, and here is the important part - constant coefficients does not have any impact in terms of time complexity and you should pay attention carefully to the size of each part. We always choose to look at the bigger picture and what would really make the difference. Therefore the best answer would be O(nlogn + nm) and not even O(n + nlogn + nm) as nlogn's growth is much faster than n's.

I would recommend reading a little bit here: https://en.wikipedia.org/wiki/Time_complexity. Should give you a clear understanding of the theory here.

TS_
  • 319
  • 1
  • 5