Time Complexity and space complexity

Time complexity

Its not the time taken. It’s the rate at which the time taken increases with respect to the input size

Rules to remember to cal TC / O() big-oh notations

Always compute TC based on worst case scenarios.

Avoid constants

avoid lower values

big O, theta, omega

big - og - worst case - upper bound

theta - avg complexity

omega - lower bound - best case

for(i = 0; i <n ; i++){

for(j=0; j<n;j++){

print

}}

O(n²)

for(i = 0; i <n ; i++){

for(j=0; j<i;j++){

print

}}

(1+2+3+4+…n) = (n* (n+1)) /2

O(n²/2 +n/2) = O(n²)

Space Complexity

Memory space that the program takes. Varies from machine to machine. So we use big oh notation.

Auxiliary space (space that we take to solve the problem) + input space (space that we take to store the input)

input → a, b

extra space → c

inp(a) inp(b)

c = a+b

we are using auxiliary space c and input a, b so the SC is O(3).

int a[n] array - SC = O(n)