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

An undirected graph g with n vertices and e edges, An undirected graph G wi... An undirected graph G with n vertices and e edges is shown by adjacency list.  What is the time required to generate all the connected components? O (e+n)

Define the external path length, Define the External Path Length The Ex... Define the External Path Length The External Path Length E of an extended binary tree is explained as the sum of the lengths of the paths - taken over all external nodes- from

Chaining Method as Method of Collision Resolution , Q. The given values are... Q. The given values are to be stored in a hash table 25, 42, 96, 101, 102, 162, 197 Explain how the values are hashed by using division technique of hashing with a table

Algorithm adjust, write the algorithm for adjust write the algorithm for adjust

Explain circular queues, Circular Queues:- A more efficient queue repre... Circular Queues:- A more efficient queue representation is get by regarding the array Q(1:n) as circular. It becomes more convenient to declare the array as Q(O: n-1), when  re

Implement an open hash table, In a chained hash table, each table entry is ... In a chained hash table, each table entry is a pointer to a collection of elements. It can be any collection that supports insert, remove, and find, but is commonly a linked list.

Exlain double linked list, Double Linked List In a doubly linked list, ... Double Linked List In a doubly linked list, also known as 2 way lists, each node is separated into 3 parts. The first part is called last pointer field. It has the address of t

Doubly linked list having n nodes, The time required to delete a node x fro... The time required to delete a node x from a doubly linked list having n nodes is O (1)

Comparisions and assignments in worst case, Q. Calculate that how many key ... Q. Calculate that how many key comparisons and assignments an insertion sort makes in its worst case?        Ans: The worst case performance occurs in insertion

Data structure for representing numbers, Your first task will be to come up... Your first task will be to come up with an appropriate data structure for representing numbers of arbitrary potential length in base 215. You will have to deal with large negative