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

How can a lock object be called in the transaction, How can a lock object b... How can a lock object be called in the transaction? By calling Enqueue and Dequeue in the transaction.

Defination, what is an algorithms what is an algorithms

Flow chart, that will determine the volume of the sphere or the volume of c... that will determine the volume of the sphere or the volume of cone or volume of pyramid depending on the choice of the user

STACK, 5. Implement a stack (write pseudo-code for STACK-EMPTY, PUSH, and P... 5. Implement a stack (write pseudo-code for STACK-EMPTY, PUSH, and POP) using a singly linked list L. The operations PUSH and POP should still take O(1) time.

A difference between linear and non linear, state difference between linear... state difference between linear and non linear data structure. give one example scenario of each

Binary search tree (bst), Q. Explain what do we understand by Binary Search... Q. Explain what do we understand by Binary Search Tree (BST)? Make a BST for the following given sequence of the numbers. 45, 32, 90, 21, 78, 65, 87, 132, 90, 96, 41, 74, 92

Explain in detail about the abstract data type, Abstract data type The ... Abstract data type The thing which makes an abstract data type abstract is that its carrier set and its operations are mathematical entities, like geometric objects or numbers;

Operations on sequential files, Insertion: Records has to be inserted at t... Insertion: Records has to be inserted at the place dictated by the sequence of keys. As is obvious, direct insertions into the main data file would lead to frequent rebuilding of

FIRST function in the compiler construction, I need a recursive algorithm t... I need a recursive algorithm to implement the FIRST function to any grammar

Siso-4bit register, explain working of siso-register to store 1011 and show... explain working of siso-register to store 1011 and show timing diagram &table