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

Euclidean algorithm, The Euclidean algorithm is an algorithm to decide the ... The Euclidean algorithm is an algorithm to decide the greatest common divisor of two positive integers. The greatest common divisor of N and M, in short GCD(M,N), is the largest in

Frequency count, what is frequency count what is frequency count

Types of tree ?, Binary: Each node has one, zero, or two children. This ... Binary: Each node has one, zero, or two children. This assertion creates many tree operations efficient and simple. Binary Search : A binary tree where each and every left

Give the example of bubble sort algorithm, Give the example of bubble sort ... Give the example of bubble sort algorithm For example List: - 7 4 5 3 1. 7 and 4 are compared 2. Since 4 3. The content of 7 is now stored in the variable which was h

Define the carrier set of the symbol abstract data type, Define the Carrier... Define the Carrier set of the Symbol ADT Carrier set of the Symbol ADT is the set of all finite sequences of characters over Unicode characters set (Unicode is a standard char

Algorithm for insertion into the circular queue, Algorithm for insertion of... Algorithm for insertion of any element into the circular queue: Step-1: If "rear" of the queue is pointing at the last position then go to step-2 or else Step-3 Step-2: make

Remainder function.., 3633(mod 11) 3633(mod 11)

Algorithm of binary search, Step 1: Declare array 'k' of size 'n' i.e. k(n)... Step 1: Declare array 'k' of size 'n' i.e. k(n) is an array which stores all the keys of a file containing 'n' records Step 2: i←0 Step 3: low←0, high←n-1 Step 4: while (l

Hash tables, Q. Explain the Hash Tables, Hash function and Hashing Techniqu... Q. Explain the Hash Tables, Hash function and Hashing Techniques properly?             A n s . H as h Table is explained as follows : A hash table is a data struc

Explain what is stack. describe ways to execute stack. , ST AC K is ... ST AC K is explained as follows : A stack is one of the most usually used data structure. A stack is also called a Last-In-First-Out (LIFO) system, is a linear list in