Calculation of storage complexity, Data Structure & Algorithms

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







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
Related Questions
Double ended queues are implemented along doubly linked lists. A doubly link list can traverse in both of the directions as it contain two pointers namely left pointers and righ

implement multiple stacks in a single dimensional array. write algorithm for various stack operation for them

What is complexity of an algorithm? What is the basic relation between the time and space complexities of an algorithm? Justify your answer by giving an example.

Determine YIQ Colour Model Whereas an RGB monitor requires separate signals for the red, green, and blue components of an image, a television monitor uses a single composite si

Construct G for α, n, and W given as command line parameters. Throw away edges that have an asymmetric relation between nodes. That is, if A is connected to B, but B is not connect


Q. Write down an algorithm to convert an infix expression into the postfix expression.     Ans. Algo rithm to convert infix expression to post fix expression is given as

Define a sparse metrics. A matrix in which number of zero entries are much higher than the number of non zero entries is known as sparse matrix. The natural method of showing m

compare two functions n and 2n for various values of n. determine when second becomes larger than first

Q. Construct a complete binary tree with depth 3 for this tree which is maintained in the memory using the linked representation. Make the adjacency list and adjacency matrix for t