Calculation of storage complexity, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Calculation of storage complexity

Recursion, difference between recursion and iteration

difference between recursion and iteration

LINKED LIST, HOW LINKED LIST HEADER WORKS? HOW TO INSERT AND DELETE ELEMENT...

HOW LINKED LIST HEADER WORKS? HOW TO INSERT AND DELETE ELEMENTS IN LINKED LIST?

Splaying algorithm, Insertion & deletion of target key requires splaying of...

Insertion & deletion of target key requires splaying of the tree. In case of insertion, the tree is splayed to find the target. If, target key is found out, then we have a duplicat

Illustrate hls colour model, HLS Colour Model  This model has the doub...

HLS Colour Model  This model has the double-cone representation shown in Figure 3.40. The three colour parameters in this model are called hue (H), lightness (L), and Saturati

Branch and bound algorithm, Suppose we have a set of N agents and a set of ...

Suppose we have a set of N agents and a set of N tasks.Each agent can only perform exactly one task and there is a cost associated with each assignment. We would like to find out a

Circular linked list, In a circular linked list There is no beginning a...

In a circular linked list There is no beginning and no end.

What is keyed access- container, What is Keyed Access- Container A c...

What is Keyed Access- Container A collection may allow its elements to be accessed by keys. For instance, maps are unstructured containers which allows their elements to be

Explain the abstract data type assertions, Explain the Abstract data type a...

Explain the Abstract data type assertions Generally, ADT assertions translate into assertions about the data types which implement ADTs, which helps insure that our ADT impleme

Difference between array and abstract data types, Difference between array ...

Difference between array and abstract data types Arrays aren't abstract data types since their arrangement in the physical memory of a computer is an essential feature of their

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd