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
In this project you will write a program to produce a discrete time simulation of a queue as shown in Fig. 1. Time is slotted on the input and the output. Each input packet follows

The below figure illustrates the BOM (Bill of Materials) for product A. The MPS (Material requirements Planning) start row in the master production schedule for product A calls for

create aset of ten numbers.then you must divide it into two sets numbers which are set of odd numbers and set of even numbers.

complete information about collision resolution techniques

explain quick sort algorithm

Threaded Binary Tree : If a node in a binary tree is not having left or right child or it is a leaf node then that absence of child node is shown by the null pointers. The spac

It does not have any cycles (circuits, or closed paths), which would imply the existence of more than one path among two nodes. It is the most general kind of tree, and might be co

Merging 4 sorted files having 50, 10, 25 and 15 records will take time

How many recursive calls are called by the naïve recursive algorithm for binomial coefficients, C(10, 5) and C(21, 12) C(n,k){c(n-1,k)+c(n-1,k-1) if 1 1 if k = n or k = 0

3. A function to convert a complex number in algebraic form to a complex number in phasor form