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

Memory allocation strategies, Q. Explain the various memory allocation stra... Q. Explain the various memory allocation strategies.                                                            Ans. M e m ory Allocation Strategies are given as follow

What is assertions and abstract data types, Assertions and Abstract Data Ty... Assertions and Abstract Data Types Even though we have defined assertions in terms of programs, notion can be extended to abstract data types (which are mathematical entities).

Abstract data type-list, It is a useful tool for indicating the logical pro... It is a useful tool for indicating the logical properties of data type. It is a collection of values & a set of operations on those values. Methodically, "a TYPE is a set, & elemen

Implementation of queue, For a queue a physical analogy is a line at bookin... For a queue a physical analogy is a line at booking counter. At booking counter, customers go to the rear (end) of the line & customers are attended to several services from the fr

Write an algorithm to find outputs number of cars, A company is carrying ou... A company is carrying out a survey by observing traffic at a road junction. Every time a car, bus or lorry passed by road junction it was noted down. 10 000 vehicles were counted d

Algorithm, algorithm to search a node in linked list algorithm to search a node in linked list

Matrix stored in memory, Method to measure address of any element of a matr... Method to measure address of any element of a matrix stored in memory. Let us consider 2 dimensional array a of size m*n further consider that the lower bound for the row index

Define about the class invariant, Define about the class invariant A cl... Define about the class invariant A class invariant may not be true during execution of a public operation though it should be true between executions of public operations. For

Search on a hashed file, Write a program to simulate searching over a hashe... Write a program to simulate searching over a hashed file, with different assumptions for the sizeof file pages.Write a program to perform equality search operations on the hashed f

Draws a rectangular grid algorithms, Prepare a GUI called Hotplate GUI that... Prepare a GUI called Hotplate GUI that holds a central panel that draws a rectangular grid that represents Element objects which should be held in a 2-dimensional array. The applic