Since memory is becoming more & cheaper, the prominence of runtime complexity is enhancing. However, it is very much significant to analyses the amount of memory utilized by a program. If the running time of any algorithms is not good then this will take longer to execute. However, if this takes more memory (the space complexity is more) beyond the capacity of the machine then the program will not execute at all. Therefore it is more critical than run time complexity. However, the matter of respite is that memory is reutilized throughout the course of program execution.

We will analyses this for recursive & iterative programs.

For an iterative program, usually this is just a matter of looking at the variable declarations and storage allocation calls, for example number of variables, length of an array etc.

The analysis of recursive program w.r.t. space complexity is more complexes as the space utilized at any time is the total space used through all recursive calls active at that time.

Each of recursive call takes a constant amount of space & some space for local variables and function arguments, and for remembering also some space is allocated where each call must return to. General recursive calls employ linear space. That is, for n recursive calls, the space complexity is O(n).

Assume the following example: Binary Recursion (A binary-recursive routine (potentially) calls itself twice).

A.    If n equals 0 or 1, then return 1

B.     calculate recursively f (n-1)

C.     calculate recursively f (n-2)

D.    Return the total of the results from steps 2 and 3.

Posted Date: 4/4/2013 6:10:43 AM | Location : United States

Ask an Expert

Related Discussions:- Calculation of storage complexity, Assignment Help, Ask Question on Calculation of storage complexity, Get Answer, Expert's Help, Calculation of storage complexity Discussions

Write discussion on Calculation of storage complexity
Your posts are moderated

Write your message here..

Related Questions

Type of qualitative method, Type of Qualitative Method: Different  qua... Type of Qualitative Method: Different  qualitative methods are suitable for different  types of study. Quite often we can  combine  qualitative and quantitative  methods. Many

Stack, Explain in detail the algorithmic implementation of multiple stacks.... Explain in detail the algorithmic implementation of multiple stacks.

Sorting, how to do a merge sorting how to do a merge sorting

State phong shading, Phong Shading Phong shading too is based on interp... Phong Shading Phong shading too is based on interpolation, but instead of interpolating the colour value, it is the normal vector, which is interpolated for each point and a co

Multiple queue, #questionalgorithm for implementing multiple\e queues in a ... #questionalgorithm for implementing multiple\e queues in a single dimensional array

Linear search, Linear search is not the most efficient way to search an ite... Linear search is not the most efficient way to search an item within a collection of items. Though, it is extremely simple to implement. Furthermore, if the array elements are arra

Explain linked list and its types, Data Structure and Algorithm 1. Exp... Data Structure and Algorithm 1. Explain linked list and its types. How do you represent linked list in memory? 2. List and elucidate the types of binary tree. 3. Descr

What is diffuse illumination, Diffuse Illumination Diffuse illuminatio... Diffuse Illumination Diffuse illumination means light that comes from all directions not from one particular source. Think about the light of a grey cloudy day as compared to

Kruskals algorithm, Krushkal's algorithm uses the concept of forest of tree... Krushkal's algorithm uses the concept of forest of trees. At first the forest contains n single node trees (and no edges). At each of the step, we add on one (the cheapest one) edg

Multiple queue, algorithm for multiple queue with example program algorithm for multiple queue with example program