1). Loop:-
for (int i=0; i<=n; i++) ----------> n
{
a = a+b; //Constant ------------->c
}
c*n = c.n = O(n)
2). Nested Loop:- multiplication
for(int i=0; i<=n; i++) ------ > n
{ -------------> so n*n = n^2
for(int j=1; j<=n; j++) ------- > n
{
a = a+b; // Constant Time --------------> c then c*n^2 = O(n^2)
}
}
3). Consecutive Statement:- Adding
1). a = a+b; ------------------> c1
2). for(int i=0; i<=n; i++) ---------> n
{
x = x+y; ------------------> c2
}
3). for(int j=0; j<=n; j++) ------------> n
{
c = c+d; ----------------------> c3
}
So in Equation it will be:-
c1 + c2.n + c3.n ===> c1 + (c2+c3).n ========> (c1 + c2 ).n
Now neglect the constant you will get O(n)
4) If-Else Statement:-
if(condition)
{
for (int i=0; i<=n; i++) ----------> n
{
a = a+b; //Constant ------------->c
}
}
else
for(int i=0; i<=n; i++) ------ > n
{ -------------> so n*n = n^2
for(int j=1; j<=n; j++) ------- > n
{
a = a+b; // Constant Time --------------> c then c*n^2 = O(n^2)
}
}
O(n) + O(n^2) == worst case
5). Logarithmic Complexity:-
for(i=0;i<=n; )
{
i = i*2; ------------------> logn =====> O(logn)
}
Important Note:-
O(1) < O(logn) < O(n)