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

The quick sort algorithm exploit design technique, The quick sort algorithm...

The quick sort algorithm exploit design technique Divide and Conquer

The smallest element of an array''s index, The smallest element of an array...

The smallest element of an array's index is called its Lower bound.

Design the system for seller, Your program should include three components ...

Your program should include three components selling, buying and managing for the use of sellers, buyers and the Manager, respectively. Provide a menu for a user to enter each comp

Linked list implementation of a queue, The fundamental element of linked li...

The fundamental element of linked list is a "record" structure of at least two fields. The object which holds the data & refers to the next element into the list is called a node .

Design a binary search tree, Binary Search Tree usage: Write a progra...

Binary Search Tree usage: Write a program to compare the time taken for a search in a skewed tree, a balanced tree, and a random tree. Speci cally, your program should do the

What are the dynamic arrays, What are the Dynamic arrays Dynamic arrays...

What are the Dynamic arrays Dynamic arrays are convenient for programmers since they can never be too small-whenever more space is needed in a dynamic array, it can simply be e

Graph, adjacency multilist

adjacency multilist

Linked list, Write a program for reversing the Linked list

Write a program for reversing the Linked list

Define algorithm, What is an Algorithm? An algorithm is a sequence of u...

What is an Algorithm? An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for getting a needed output for any legitimate input in a finite amoun

Example of pre order traversal, Example of pre order traversal: Reading of...

Example of pre order traversal: Reading of a book, since we do not read next chapter unless we complete all sections of previous chapter & all its sections. Figure  : Rea

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