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
Question 1 Explain the following? Arrays Stack Trees Question 2 Explain the Linked list implementation of stack Question 3 What is a binary tree? Expla

Q. Draw  the structures of complete  undirected  graphs  on  one,  two,  three,  four  and  five vertices also prove that the number of edges in an n vertex complete graph is n(n-1

What is a linear array? An array is a way to reference a series of memory locations using the similar name. Every memory location is shown by an array element. An  array elemen

Draw trace table and determine output from the subsequent flowchart using below data:  X = 5, -3, 0, -3, 7, 0, 6, -11, -7, 12

Determine the importance of array Arrays are significant since they allow many values to be stored in a single data structure whereas providing very fast access to each value.

In a doubly linked list, also called as 2 way list, each node is divided into 3 parts. The first part is called previous pointer field. It contains the address of the preceding

Program will demonstrate deletion of an element from the linear array /* declaration of delete_list function */ voiddelete_list(list *, int); /* definition of delete_list

Task If quicksort is so quick, why bother with anything else? If bubble sort is so bad, why even mention it? For that matter, why are there so many sorting algorithms? Your

Containers Introduction Simple abstract data types are useful for manipulating simple sets of values, such as integers or real numbers however more complex abstract data t

The best average behaviour is shown by  Quick Sort