Space-complexity of the algorithm, Data Structure & Algorithms

The space-complexity of the algorithm is a constant. It just needs space of three integers m, n and t. Thus, the space complexity is O(1).

The time complexity based on the loop and on the condition whether m>n or not. The real issue is how much iteration occurs? The answer based on both m and n.

Best case: If m = n, then there is only one iteration. O(1)

Worst case: If n = 1, then there will m iterations; It is the worst-case (also equivalently, if m = 1 there are n iterations) O(n).

The space complexity of a computer program is the amount of memory needed for its proper execution. The significant concept behind space needed is that unlike time, space can be reused throughout the execution of the program. As discussed, there is frequently a trade-off among the time and space needed to run a program.

In formal definition, the space complexity is described as follows:

Space complexity of Turing Machine: worst case maximum length of the tape needed to process an input string of length n.

The class PSPACE, in complexity theory, is the set of decision problems which can be solved through a Turing machine by using a polynomial amount of memory, and unlimited time.

Posted Date: 4/4/2013 6:17:59 AM | Location : United States

Related Discussions:- Space-complexity of the algorithm, Assignment Help, Ask Question on Space-complexity of the algorithm, Get Answer, Expert's Help, Space-complexity of the algorithm Discussions

Write discussion on Space-complexity of the algorithm
Your posts are moderated
Related Questions
what is tree

Example: (Double left rotation while a new node is added into the AVL tree (RL rotation)) Figure: Double left rotation when a new node is inserted into the AVL tree A

Difference among Prism's and Kruskal's Algorithm In Kruskal's algorithm, the set A is a forest. The safe edge added to A is always a least-weight edge in the paragraph that lin

State in detail about the Integer Carrier set of the Integer ADT is the set {..., -2, -1, 0, 1, 2, ...}, and  operations on these values are addition, multiplication, subtrac

In this part, students are allowed to implement the following simplifications in their table and data design. o Availability for the beauty therapists don't have to be considere

Q. Can a Queue be represented by circular linked list with only one pointer pointing to the tail of the queue? Substantiate your answer using an example. A n s . Yes a

Advantages of First in First out (FIFO) Costing Advantages claimed for first in first  out (FIFO)  costing method are: 1. Materials used are drawn from the cost record in

Define data model?  A data model is a collection of conceptual tools for explaning data, data relationships, data semantics and consistency constraints.

#What is the pointer

Explain about the String Abstract data type operations Symbol ADT has no concatenation operations, but presuming we have a full-featured String ADT, symbols can be concatenated