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
Write an algorithm for getting solution to the Tower's of Hanoi problem. Explain the working of your algorithm (with 4 disks) with appropriate diagrams. Ans: void Hanoi(int

Post order traversal: The children of node are visited before the node itself; the root is visited last. Each node is visited after its descendents are visited. Algorithm fo

In this respect depth-first search (DFS) is the exact reverse process: whenever it sends a new node, it immediately continues to extend from it. It sends back to previously explore

write a COBOL program to find the biggest of two numbers

The number of different directed trees with 3 nodes are ?? The number of disimilar directed trees with three nodes are 3

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

The number of leaf nodes in a complete binary tree of depth d is    2 d


Write a function that performs the integer mod function. Given the previous functions you have implemented already, this one should be a piece of cake. This function will find the

The most common way to insert nodes to a general tree is to first discover the desired parent of the node you desire to insert, and then insert the node to the parent's child list.