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

Time complexity, Run time complexity of an algorithm is depend on Run time complexity of an algorithm is depend on

Algorithsm, What are the properties of an algorithsm? What are the properties of an algorithsm?

The quick sort algorithm exploit design technique, The quick sort algorithm... The quick sort algorithm exploit design technique Divide and Conquer

What is a binary search tree (bst), What is a Binary Search Tree (BST)? ... What is a Binary Search Tree (BST)? A binary search tree B is a binary tree every node of which satisfies the three conditions: 1.  The value of the left-subtree of 'x' is le

Deletion of an element from the linked list, A LGORITHM (Deletion of an ele... A LGORITHM (Deletion of an element from the linked list) Step 1  Begin Step 2  if the list is empty, then element cannot be deleted Step 3  else, if the element to be del

Binary search tree, write an algorithm to delete an element x from binary... write an algorithm to delete an element x from binary search with time complex

Explain time complexity, Time Complexity, Big O notation The amount of ... Time Complexity, Big O notation The amount of time needed by an algorithm to run to its completion is referred as time complexity. The asymptotic running time of an algorithm i

Graph with n vertices will absolutely have a parallel edge, A graph with n ... A graph with n vertices will absolutely have a parallel edge or self loop if the total number of edges is greater than n-1

Non Recursive Algorithm to Traverse a Binary Tree, Q. Write down a non recu... Q. Write down a non recursive algorithm to traverse a binary tree in order.                    Ans: N on - recursive algorithm to traverse a binary tree in inorder is as

#binary search, Ask question #Minima binary search tree is used to locate t... Ask question #Minima binary search tree is used to locate the number 43 which of the following probe sequences are possible and which are not? explainum 100 words accepted#