Determination of Time Complexity

The RAM Model

The random access model (RAM) of computation was devised through John von Neumann to study algorithms. In computer science, Algorithms are studied since they are independent of machine & language.

We will do all our design & analysis of algorithms depend on RAM model of computation:

• Each "simple" operation (+, -, =, if, call) takes 1 step exactly.
• Loops & subroutine calls are not easy operations, but based upon the size of the data and the contents of a subroutine.
• Each of the memory access takes 1 step exactly.

The complexity of algorithms by using big-O notation can be described in the following way for a problem of size n:

• Constant-time method is "order 1" : O(1). The time that needed is constant independent of the input size.
• Linear-time method is "order n": O(n). The time needed is proportional to the input size. If input size doubles, then, the time to run the algorithm also will be doubles.
• Quadratic-time method is "order N squared": O(n²). The time that needed is proportional to the square of input size. If the input size doubles, then, the time needed will enhance by four times.

The procedure of analysis of algorithm (program) involves analyzing each of the step of the algorithm. It based on the kinds of statements utilized in the program.

Posted Date: 4/4/2013 5:50:33 AM | Location : United States

Ask an Expert

Related Discussions:- Determination of time complexity, Assignment Help, Ask Question on Determination of time complexity, Get Answer, Expert's Help, Determination of time complexity Discussions

Write discussion on Determination of time complexity
Your posts are moderated

Write your message here..

Related Questions

What are the specific needs for realism, Normal 0 false false... Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

#title.structured programming, what do you understand by structured program... what do you understand by structured programming?explain with eg. top down and bottem up programming technique

Write an algorithm to illustrate this repeated calculation, The below formu... The below formula is used to calculate n: n = (x * x)/ (1 - x). Value x = 0 is used to stop the algorithm. Calculation is repeated using values of x until value x = 0 is input. The

Depth First Search Through Un-weighted Connected Graph , Q. Write down the ... Q. Write down the algorithm which does depth first search through an un-weighted connected graph. In an un-weighted graph, would breadth first search or depth first search or neith

Splay trees, Addition of new records in a Binary tree structure always occu... Addition of new records in a Binary tree structure always occurs as leaf nodes, which are further away from the root node making their access slower. If this new record is to be ac

Standard ways of traversing a graph, Q. Which are the two standard ways of ... Q. Which are the two standard ways of traversing a graph?  Explain them with an example of each.  Ans:   T he two ways of traversing a graph are written below

State phong shading, Phong Shading Phong shading too is based on interp... Phong Shading Phong shading too is based on interpolation, but instead of interpolating the colour value, it is the normal vector, which is interpolated for each point and a co

If a node having two children is deleted from a binary tree, If a node havi... If a node having two children is deleted from a binary tree, it is replaced by?? Inorder successor

Explain space complexity, Explain Space Complexity Space Complexity :... Explain Space Complexity Space Complexity :- The space complexity of an algorithm is the amount of memory it requires to run to completion. Some of the reasons to study space

Algorithm for pre-order traversal, Hear is given a set of input representin... Hear is given a set of input representing the nodes of a binary tree, write a non recursive algorithm that must be able to give the output in three traversal orders. Write down an