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
Determine about the Post conditions assertion A  post condition is an assertion which should be true at completion of an operation. For instance, a post condition of the squ

How do collisions happen during hashing? Usually the key space is much larger than the address space, thus, many keys are mapped to the same address. Assume that two keys K1 an

Q. Show the various passes of bubble sort on the unsorted given list 11, 15, 2, 13, 6           Ans: The given data is as follows:- Pass 1:-     11   15   2     13

If a node in a BST has two children, then its inorder predecessor has No right child

A database is a collection of data organized in a manner that facilitates updation, retrieval and management of the data. Searching an unindexed database having n keys will have a

ST AC K is explained as follows : A stack is one of the most usually used data structure. A stack is also called a Last-In-First-Out (LIFO) system, is a linear list in

The ?-Notation (Lower Bound) This notation provides a lower bound for a function to within a constant factor. We write f(n) = ?(g(n)), if there are positive constants n 0 and

Each data record contains a fixed place in a relative file. Each record ought to have associated with it in integer key value which will help identify this slot. Therefore, this ke

QUESTION Explain the following data structures: (a) List (b) Stack (c) Queues Note : your explanation should consist of the definition, operations and examples.