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
A representation of an array structure is a mapping of the (abstract) array with elements of type T onto the store which is an array with elements of type BYTE. The array could be

Q. Explain w hat are the stacks? How can we use the stacks  to check whether an expression is correctly parentheses or not. For example (()) is well formed but (() or )()( is not w

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 .

how we can convert a graph into tree

Byteland county is very famous for luminous jewels. Luminous jewels are used in making beautiful necklaces. A necklace consists of various luminous jewels of particular colour. Nec

WRITE AN ALGORITHM TO CONVERT PARENTHIZED INFIX TO POSTFIX FORM ALSO TRACE ALG ON ((A+B)*C-(D-E)$F+G)

Materials consumed are priced in a systematic and realistic manner. It is argued that current acquisition costs are incurred for the purpose of meeting current production and sales

Multilist Representation of graph

State about the Bit String Carrier set of the Bit String ADT is the set of all finite sequences of bits, including empty strings of bits, which we denote λ. This set is {λ, 0

Q. State the difference between a grounded header link list and a circular header link list?     Ans: A header linked list is a linked list which all the time c