Time and Space Complexity

What is Time Complexity?

Time Complexity is rate of increase in time with respect to the input size.

means on what rate, time is increasing when we increase the input size. for example if we double the input size then in what rate, time to execute that code will increase , will it also get doubled, will it get tripled. we call that rate the time complexity of our programme.

we denoted it as big oh notation - o(  )

Rules of Time Complexity

• Always calculate time complexity in terms of worst case
• Avoid the constant values
• Ignore the lower bound

Different types of Time Complexity

• Big oh ( o ) : worst case
• Theta (  ) : average case
• Omega ( ) : best case 

Examples:

What is Space Complexity ?

Space complexity is the amount of memory an algorithm needs to run, as a function of the input size.

It's also denoted by big oh notation (  )

Important Terms

• Auxiliary Space : the extra space used to solve the problem 
• Input Space : the space used to store the input

For example : 

a = 3, b = 5 , c = 6

total = a + b + c

print ( total )

Here, 

• a , b, c are the inputs so space it will take to store is called input space
• total here is the extra variable we are taking to add the inputs , so space it will take will be called auxiliary space

How to calculate the Space Complexity

• Auxiliary Space + Input Space