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
Problem 1. You are asked to store Names of all 100 students of class A in your Learning Centre. Which data type will you use? What is its syntax? Explaining the data typ

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

pls i want a psuedo code for hotel reservation system.

algorithm for multiplication of two sparse matrices using link list

Determine about the push operation A Container may or may not be accessible by keys, so it can't make assumptions about element retrieval methods (for example, it cannot have a

#question bubble sort..

Q. Enumerate number of operations possible on ordered lists and arrays.  Write procedures to insert and delete an element in to array.


Merge sort is also one of the 'divide & conquer' classes of algorithms. The fundamental idea in it is to split the list in a number of sublists, sort each of these sublists & merge

Q. Convert the given infix expression into the postfix expression (also Show the steps) A ∗ (B + D)/ E - F(G + H / k ) Ans. Steps showing Infix to Post fix