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
Q. By making use of stacks, write an algorithm to determine whether the infix expression has balanced parenthesis or not.

Explain the term - Branching There are two common ways of branching: case of ..... otherwise ...... endcase  if ..... then ..... else ..... endif   case of

Q. State the difference between a grounded header link list and a circular header link list?     Ans: A header linked list is a linked list which all the time c

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

Explain the term totalling To add up a series numbers the subsequent type of statement must be used: Total = total + number  This literally means (new) total = (old) t

Simplifying Assumptions of wire frame representation Neglect colour - consider Intensity: For now we shall forget about colour and restrict our discussion just to the intensi

A LGORITHM (Deletion of an element from the linked list) Step 1  Begin Step 2  if the list is empty, then element cannot be deleted Step 3  else, if the element to be del

When there is requirement to access records sequentially by some key value and also to access records directly by the similar key value, the collection of records may be organized

In any singly linked list, each of the elements contains a pointer to the next element. We have illustrated this before. In single linked list, traversing is probable only in one d