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

Ask an Expert

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

Write your message here..

Related Questions

Multiple queue, How to create multiple queue on single array? How to create multiple queue on single array?

Deletion of a node from a binary search tree, The algorithm to delete any n... The algorithm to delete any node having key from a binary search tree is not simple where as several cases has to be considered. If the node to be deleted contains no sons,

Non-recursive implementation of preorder traversal, For preorder traversal,... For preorder traversal, in the worst case, the stack will rise to size n/2, where n refer to number of nodes in the tree. Another method of traversing binary tree non-recursively t

Explain open addressing, Open addressing The easiest way to resolve a c... Open addressing The easiest way to resolve a collision is to start with the hash address and do a sequential search by the table for an empty location.

How many nodes in a tree have no ancestor, How many nodes in a tree have no... How many nodes in a tree have no ancestors 1 node in atree have no ancestors.

Threads in main method, Create main method or a test class that creates 2 E... Create main method or a test class that creates 2 Element objects that are neighbours of each other, the first element temperature set at 100, the 2nd at 0 and use an appropriate h

The search trees are abstract data types, the above title please send give ... the above title please send give for the pdf file and word file

Array, how to define the size of array how to define the size of array

A full binary tree with 2n+1 nodes, A full binary tree with 2n+1 nodes have... A full binary tree with 2n+1 nodes have n non-leaf nodes

Graph, For the following graph find the adjacency matrix and adjacency list... For the following graph find the adjacency matrix and adjacency list representation of the graph.