Determination of time complexity, Data Structure & Algorithms

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(n2). 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







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
Related Questions
Step-1: For the current node, verify whether it contain a left child. If it has, then go to step-2 or else go to step-3 Step-2: Repeat step-1 for left child Step-3: Visit (th

Search engines employ software robots to survey the Web & build their databases. Web documents retrieved & indexed through keywords. While you enter a query at search engine websit

State the range of operation of ADT Operations of the Range of T ADT includes following, where a, b ∈ T and r and s are values of Range of T: a...b-returns a range value (an

Write an algorithm for getting solution to the Tower's of Hanoi problem. Explain the working of your algorithm (with 4 disks) with appropriate diagrams. Ans: void Hanoi(int

A database is a collection of data organized in a manner that facilitates updation, retrieval and management of the data. Searching an unindexed database having n keys will have a

A B-tree of minimum degree t can maximum pointers in a node T pointers in a node.

Merge sort is a sorting algorithm which uses the basic idea of divide and conquers. This algorithm initially divides the array into two halves, sorts them separately and then merge

After learning this, you will be able to: understand the concept of algorithm; understand mathematical foundation underlying the analysis of algorithm; to understand se

A graph G might be defined as a finite set V of vertices & a set E of edges (pair of connected vertices). The notation utilized is as follows: Graph G = (V, E) Consider the g

explanation of doubly linklist