data structures using [end of ifstep end write an algorithm to find the sum of first natural numbers step input step set sum step repeat step while < step set sum sum set [end of loopstep print sum step end time and space complexity analysing an algorithm means determining the amount of resources (such as time and memoryneeded to execute it algorithms are generally designed to work with an arbitrary number of inputsso the efficiency or complexity of an algorithm is stated in terms of time and space complexity the time complexity of an algorithm is basically the running time of program as function of the input size similarlythe space complexity of an algorithm is the amount of computer memory that is required during the program execution as function of the input size in other wordsthe number of machine instructions which program executes is called its time complexity this number is primarily dependent on the size of the program' input and the algorithm used generallythe space needed by program depends on the following two partsfixed partit varies from problem to problem it includes the space needed for storing instructionsconstantsvariablesand structured variables (like arrays and structuresvariable partit varies from program to program it includes the space needed for recursion stackand for structured variables that are allocated space dynamically during the runtime of program howeverrunning time requirements are more critical than memory requirements thereforein this sectionwe will concentrate on the running time efficiency of algorithms worst-caseaverage-casebest-caseand amortized time complexity worst-case running time this denotes the behaviour of an algorithm with respect to the worstpossible case of the input instance the worst-case running time of an algorithm is an upper bound on the running time for any input thereforehaving the knowledge of worst-case running time gives us an assurance that the algorithm will never go beyond this time limit average-case running time the average-case running time of an algorithm is an estimate of the running time for an 'averageinput it specifies the expected behaviour of the algorithm when the input is randomly drawn from given distribution average-case running time assumes that all inputs of given size are equally likely best-case running time the term 'best-case performanceis used to analyse an algorithm under optimal conditions for examplethe best case for simple linear search on an array occurs when the desired element is the first in the list howeverwhile developing and choosing an algorithm to solve problemwe hardly base our decision on the best-case performance it is always recommended to improve the average performance and the worst-case performance of an algorithm amortized running time amortized running time refers to the time required to perform sequence of (relatedoperations averaged over all the operations performed amortized analysis guarantees the average performance of each operation in the worst case