Time Complexity Analysis (Examples)

O(1):
int main()
{
    c = a+b; o(1);
    d = b+c; O(1);
}

********************************************************************

O(cN + c) = O(N)

int main()
{
    for(int i = 0; i<15; i++)
    {
        ///O(1) expressions
    }

}

********************************************************************

O(N):
for(int i = 0; i<N; i++)
{
    o(N);
}


********************************************************************

O(N+M):
for(int i = 0; i<N; i++)
{
    ///o(1) expressions
}
for(int i = 0; i<M; i++)
{
    ///o(1) expressions
}

if(N==M) O(N+N) = O(2N) = O(N)
if(M is constant) O(N+M) = O(N)


********************************************************************

O(N*M):
for(int i = 0; i<N; i++)
{
    for(int j = 0; j<M; j++)
    {
        ///o(1) expressions
    }

    O(1)
    O(1)
    .
    .
    .
    O(1)
}

Explanation:

i   j
0   M
1   M
2   M
3   M
....
N   M

O(NM)

if(N==M) O(N^2)

********************************************************************

O(N):

for(int i = 1; i<=n; i += 2)
{
    //O(1)
}

O(1)
O(1)
.
.
.
.


i
1
3
5
.
.
.
K


k = N
O(N)

********************************************************************

O(logN):

c = constant
for(int i = 1; i<= N ; i = i*c)
{
    //O(1)
}

i
1, C, C^2, C^3, .... , C^K

C^K = N
K = logN -> log er base C
O(logN) -> where base is constant C

********************************************************************

O(logN):

for(int i = N; i> 0; i = i/2)

i
N/2
N/4
N/8
.
.
.
N/2^k

N/2^k = 1
2^k = N
k = logN

********************************************************************

O(sqrt(N)):

for(i = 1; i*i <= n; i++)
{
    //O(1)
}

i
1
4
9
16
.
.
k^2

K^2 = N

k = sqrt(N)

O(sqrt(N))

********************************************************************

O(sqrt(N)):

c = 0;
for(i = 1; c<=n; i++)
{
    c = c+i;
}


c=0, i = 1
while(c<=n)
{
    c = c+i;
    i = i+1;
}


Explanation:

i   c
1   1
2   1+2
3   1+2+3
4   1+2+3+4
5   1+2+3+4+5
.
.
.
k   1+2+3+4+5+....+k

1+2+3+4+5+....+k = N
K(K+1)/2 = N
K^2 + K = 2N
K^2 = 2N - k
k = sqrt(N)

O(sqrt(N))

********************************************************************

O(log(logN)):
for(int i = 2; i<=n; i = i*i)
{
    //some O(1) expression
}

i
2
2^2
2^(2^2)
2^(2^3)
2^(2^4)
.
.
.
2^(2^k)

2^(2^k) = N
2^K = logN
K= log(logN)


********************************************************************

O(logN + log(log(N))):

c = 0
for(int i = 1; i<=n; i = i*2)
{
    c = c+1;
}
for(int j = 1; j<=c; j = j*2)
{
    ///O(1) expression
}


complexity of 1st loop: c = O(logN)
complexity of 2nd loop: k = O(logC) = O(log(log(N)))


total = O(logN + log(log(N)))


********************************************************************

int a,b; /// a,b > 0
while(a!=b)
{
    if(a>b) a = a-b;
    else b = b-a;
}

in worst-case O(max(a,b))

********************************************************************


Computational Complexity:

int t;
while(t--)
{
    for(int i = 0; i<n; i++)
    {
        ///
    }
    for(int i = 0; i<m; i++)
    {
        ///
    }
    for(int i = 0; i<1000; i++)
    {

    }
}

t = 50

1<= m <= 10^5
1<= n <= 10^8

time : 1 sec

T(N) =  50*(10^8 + 10^5 + 1000)



/// Google Doc Link: https://docs.google.com/document/d/1juxI-0k_3rUWUXbpzVqapi0cm-41fNh71JapyLMPcUM/edit?usp=sharing