So, now lets see how to know the Big-oh complexity for a given competitive programming questions.So follow this approach -
1.In all the platforms, you will be given a time limit in seconds according to the language you choose.Some platforms may not give you time limit for your programming language directly ,so calculate it as-
a. Codechef - codechef calculation -So,as said in the article multiply your language multiplier given here with the time limit given in the problem.
Ex- If time limit given in the problem is 2 sec ,then for Java multiplier is 2X,thus
time limit for Java = 4 sec
b. For hackerrank, refer this-Hackerrank Time
Similarly you can see by yourself to get the time limit for your language.We will calculate for C++.Thus for C++,its mostly 2 sec /given in problem (multiplier is 1 ,s no problem).
2.Now you need to calculate the no. of operations your programming language can compute in 1 sec.
So for C/C++ its usually around 10^8 operations per sec.
Similarly you can see for other languages.
3.Once you have got the time limit for your programming language ,now you need to calculate the total no. of operations for the given problem.For ex-
a.If n is test case limit and m is input limit then ,worst case no. of operations performed will be-
m*n.
so if m*n =N
So, for a 1sec time limit, (keeping 10^8 operations per sec in mind)
N>10^8: better than O(N), maybe O(nlogn)
N=10^6-10^7 : O(n) solution is required.
N=10^5 : O(nlogn) solution.
N=10^4 : O(n^1.5 or n(logn)^2) solution.
N=10^3 : O(n^2) solution.
N=10^2 :O(n^3) solution.
N=10:O(n!) and O(2^n) solution.
Above will be valid for java if time limit is 2 sec.But in all platform time limit is given wrt C++.So,just look at the above always.
For ex, let say you want to know above template for java on hackerrank.So,on hackerrank java is 4 sec ,but anyway we will look at C++.For C++, its 2 sec.
which means,template is-
N>2 X 10^8: better than O(N), maybe O(nlogn)
N=2 X 10^6-10^7 : O(n) solution is required.
N=2 X 10^5 : O(nlogn) solution.
N=2 X 10^4 : O(n^1.5 or n(logn)^2) solution.
N=2 X 10^3 : O(n^2) solution.
N=2 X 10^2 :O(n^3) solution.
N=2 X 10:O(n!) and O(2^n) solution.
1.In all the platforms, you will be given a time limit in seconds according to the language you choose.Some platforms may not give you time limit for your programming language directly ,so calculate it as-
a. Codechef - codechef calculation -So,as said in the article multiply your language multiplier given here with the time limit given in the problem.
Ex- If time limit given in the problem is 2 sec ,then for Java multiplier is 2X,thus
time limit for Java = 4 sec
b. For hackerrank, refer this-Hackerrank Time
Similarly you can see by yourself to get the time limit for your language.We will calculate for C++.Thus for C++,its mostly 2 sec /given in problem (multiplier is 1 ,s no problem).
2.Now you need to calculate the no. of operations your programming language can compute in 1 sec.
So for C/C++ its usually around 10^8 operations per sec.
Similarly you can see for other languages.
3.Once you have got the time limit for your programming language ,now you need to calculate the total no. of operations for the given problem.For ex-
a.If n is test case limit and m is input limit then ,worst case no. of operations performed will be-
m*n.
so if m*n =N
So, for a 1sec time limit, (keeping 10^8 operations per sec in mind)
N>10^8: better than O(N), maybe O(nlogn)
N=10^6-10^7 : O(n) solution is required.
N=10^5 : O(nlogn) solution.
N=10^4 : O(n^1.5 or n(logn)^2) solution.
N=10^3 : O(n^2) solution.
N=10^2 :O(n^3) solution.
N=10:O(n!) and O(2^n) solution.
Above will be valid for java if time limit is 2 sec.But in all platform time limit is given wrt C++.So,just look at the above always.
For ex, let say you want to know above template for java on hackerrank.So,on hackerrank java is 4 sec ,but anyway we will look at C++.For C++, its 2 sec.
which means,template is-
N>2 X 10^8: better than O(N), maybe O(nlogn)
N=2 X 10^6-10^7 : O(n) solution is required.
N=2 X 10^5 : O(nlogn) solution.
N=2 X 10^4 : O(n^1.5 or n(logn)^2) solution.
N=2 X 10^3 : O(n^2) solution.
N=2 X 10^2 :O(n^3) solution.
N=2 X 10:O(n!) and O(2^n) solution.