You need to login before you can make any post submission.
Asymptotic notations are mathematical tools to represent time complexity of algorithms for asymptotic analysis.
The theta notation bounds a functions from above and below, so it defines exact asymptotic behavior.
For a given function g(n), we denote Θ(g(n)) is following set of functions.
Θ(g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 <= c1g(n) <= f(n) <= c2g(n) for all n >= n0}
The Big O notation defines an upper bound of an algorithm, it bounds a function only from above.
O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 <= f(n) <= c*g(n) for all n >= n0}
Just as Big O notation provides an asymptotic upper bound on a function, Ω notation provides an asymptotic lower bound.
Ω (g(n)) = {f(n): there exist positive constants c and n0 such that 0 <= c*g(n) <= f(n) for all n >= n0}.
Time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain loop, recursion and call to any other non-constant time function.
// set of non-recursive and non-loop statements
Example: swap() function has O(1) time complexity.
Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount.
Example: following functions have O(n) time complexity.
// Here c is a positive integer constant
for (int i = 1; i <= n; i += c) {
// some O(1) expressions
}
Time complexity of nested loops is equal to the number of times the innermost statement is executed.
Example: The following sample loops have O(n^{2}) time complexity
for (int i = 1; i <=n; i += c) {
for (int j = 1; j <=n; j += c) {
// some O(1) expressions
}
}
Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount.
for (int i = 1; i <=n; i *= c) {
// some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
// some O(1) expressions
}
Example: Binary Search(refer iterative implementation) has O(Log n) time complexity.
Let us see mathematically how it is O(Log n): The series that we get in first loop is 1, c, c2, c3, … ck. So now, ck = n then k = logcn and hence O( Log n)
Time Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased exponentially by a constant amount.
// Here c is a constant greater than 1
for (int i = 2; i <=n; i = pow(i, c)) {
// some O(1) expressions
}
//Here root is sqrt or cuberoot or any other constant root
for (int i = n; i > 0; i = root(i)) {
// some O(1) expressions
}
Many algorithms are recursive in nature. When we analyze them, we get a recurrence relation for time complexity.
Example: Merge Sort: T(n) = 2T(n/2) + cn
There are many other algorithms like Binary Search, Tower of Hanoi, etc.
Methods to solve Recurrences:
We make a guess for the solution and then we use mathematical induction to prove the guess is correct or incorrect.
Example: Consider the recurrence T(n) = 2T(n/2) + n
We guess the solution as T(n) = O(nLogn). Now we use induction to prove our guess.
We need to prove that T(n) <= cnLogn. We can assume that it is true for values smaller than n.
T(n) = 2T(n/2) + n
<= cn/2Log(n/2) + n
= cnLogn - cnLog2 + n
= cnLogn - cn + n
<= cnLogn
Recursion Examples:
int recursiveFun1(int n){
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
/* === Second Type in Master Theorem ===
T(n) = T(n-1) + O(1)
a = 1, b = 1, c = 0
a = 1 => Case-2 of Second Type in Master Theorem
T(n) = O(n^(c+1)) = O(n)
*/
int recursiveFun2(int n){
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
/* === Second Type in Master Theorem ===
T(n) = T(n-5) + O(1)
a = 1, b = 5, c = 0
a = 1 => Case-2 of Second Type in Master Theorem
T(n) = O(n^(c+1)) = O(n)
*/
int recursiveFun3(int n){
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
/* === First Type in Master Theorem ===
T(n) = T(n/5) + O(1)
a = 1, b = 5, c = 0
logb(a) = log5(1) = 0
c = logb(a) => Case-2 of First Type in Master Theorem
T(n) = O(n^c logn) = O(log5(n))
*/
void recursiveFun4(int n, int m, int o){
if (n <= 0)
printf("%d, %d\n",m, o);
else {
recursiveFun4(n-1, m+1, o);
recursiveFun4(n-1, m, o+1);
}
}
/* === Second Type in Master Theorem ===
T(n) = 2T(n-1) + O(1)
a = 2, b = 1, c = 0
a > 1 => Case-3 of Second Type in Master Theorem
T(n) = O(n^c * a^(n/b)) = O(2^n)
*/
int recursiveFun5(int n){
for (i = 0; i < n; i += 2) {
// do something
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
}
/* === Second Type in Master Theorem ===
T(n) = T(n-5) + O(n)
a = 1, b = 5, c = 1
a=1 => Case-2 of Second Type in Master Theorem
T(n) = O(n^(c+1)) = O(n^2)
*/
The classification is done on based on the running time (or memory) that an algorithm takes for solving the problem.
Problems with lower rate of growth are called easy problems (easy solved problems).
Problems with higher rate of growth are called hard problems (hard solved problems).
A decision problem is a question with yes/no answer and the answer depends on the values of the input.
Solving a given decision problem with an algorithm is called decision procedure for that problem.
Opposite or complement of NP.
If the answer to a problem Co-NP is “NO”, then there is a proof of this fact that can be checked in polynomial time.
Relationship between P, NP, Co-NP:
Any problem in P is also in NP coz if a problem is in P, we can verify “YES” answer in polynomial time.
Similarly any problem in P is also in Co-NP coz if a problem is in P, we can verify “NO” answer in polynomial time.
One of the important open questions in theoretical computer science is whether or not P=NP (Nobody knows).
Intuitively it should be obvious that P≠NP, but nobody knows how to prove it.
Another open questions is whether NP and Co-NP are different (Nobody knows).
Even if we can verify every “YES” answer quickly, there’s no reason to think we can also verify “NO” answers quickly.
It is generally believed that NP≠Co-NP, but again nobody knows how to prove it.
Class of decision problems which are at least as hard as the hardest problems in NP.
Every Problem in NP can be reduced to it.
A problem K is NP-Hard indicates that if a polynomial-time algorithm exists for K then a polynomial-time algorithm exists for every problem in NP.
K is NP-hard implies that if K can be solved in polynomial-time, then P=NP.
Although it is suspected that there are no polynomial-time algorithms for NP-hard problems, this has not been proven.
All NP-Hard problems are not in NP, so it takes a long time to even check them (forget about solving) and it may not even be decidable.
NP-hard are not only restricted to decision problems, for instance it also includes search problems, or optimization problems.
A problem is NP-Complete if it is part of both NP-hard and NP.
Class of decision problems which contains the hardest problems in NP (but remember there can be even more harder problem outside NP in NP-Hard class).
Each NP-complete problem has to be in NP.
If anyone finds a polynomial-time algorithm for one NP-Complete problem, then we can find polynomial-time algorithm for every NP-Complete problem.
We can check an answer fast and every problem in NP reduces to it.
Example: Subset-Sum (NP-Complete)
Relationship between P, NP, Co-NP, NP-Hard and NP-Complete
NP-Complete problems are strict subset of problems that are NP-Hard or NP-Hard is strict superset of NP-Complete.
Some problems are NP-Hard but not in NP.
NP-Hard problems might be impossible to solve in general.
We can tell the difference in difficulty b/w NP-Hard and NP-Complete coz NP includes everything easier than it’s toughest problem.
But if a problem is not in NP, it is harder than all problems in NP.
NP-Hard Class Problems
Example-1:
void fun(){
int i, j;
for (i=1; i<=n; i++)
for (j=1; j<=log(i); j++)
printf("GeeksforGeeks");
}
/* Θ(log 1) + Θ(log 2) + Θ(log 3) + . . . . + Θ(log n) = Θ(log n!) = Θ(nlogn) coz n!≈nn/2
T(n) = Θ(nlogn) */
Example-2:
void fun(int n){
int j = 1, i = 0;
while (i < n){
// Some O(1) task
i = i + j;
j++;
}
}
/* The value of i is incremented by 1,2,3,4, . . . and so on
So the value of i will be like 0, 1, 3, 6, 10, 15, . . . : We can see that kth term will be k(k+1)/2
k(k+1)/2 = n => k2/2 = n => k = √n
T(n) = Θ(√n) *