simplistic introduction to algorithmic complexity consider def factorial( )"""assumes that is positive int returns !""if = return elsereturn *factorial( - there are no loops in this codeso in order to analyze the complexity we need to figure out how many recursive calls get made the series of calls is simply factorial( )factorial( - )factorial( - )factorial( the length of this seriesand thus the complexity of the functionis (xthus far in this we have looked only at the time complexity of our code this is fine for algorithms that use constant amount of spacebut this implementation of factorial does not have that property as we discussed in each recursive call of factorial causes new stack frame to be allocatedand that frame continues to occupy memory until the call returns at the maximum depth of recursionthis code will have allocated stack framesso the space complexity is (xthe impact of space complexity is harder to appreciate than the impact of time complexity whether program takes one minute or two minutes to complete is quite visible to its userbut whether it uses one megabyte or two megabytes of memory is largely invisible to users this is why people typically give more attention to time complexity than to space complexity the exception occurs when program needs more space than is available in the main memory of the machine on which it is run log-linear complexity this is slightly more complicated than the complexity classes we have looked at thus far it involves the product of two termseach of which depends upon the size of the inputs it is an important classbecause many practical algorithms are log-linear the most commonly used log-linear algorithm is probably merge sortwhich is ( log( ))where is the length of the list being sorted we will look at that algorithm and analyze its complexity in the next polynomial complexity the most commonly used polynomial algorithms are quadratici their complexity grows as the square of the size of their input considerfor examplethe function in figure which implements subset test