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
characteristics of a good algorithm

Varieties of Arrays In some languages, size of an array should be established once and for all at program design time and can't change during execution. Such arrays are known a

how I can easily implement the bubble,selection,linear,binary searth algorithms?

Q. Write a procedure to the insert a node into the linked list at a particular position and draw the same by taking an example?

Q. Develop a representation for a list where insertions and deletions can be done at either end. Such a structure is known as a Deque (Double ended queue). Write functions for inse

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

In the last subsection, we have implemented a stack by using an array. While a stack is implemented by using arrays, it suffers from the basic restriction of an array - i.e., its s

Gouraud Shading The faceted appearance of a Lambert shaded model is due to each polygon having only a single colour. To avoid this effect, it is necessary to vary the colour ac

Q. By giving an example show how multidimensional array can be represented in one the dimensional array.

I need to know about data structure and algorithms. can you help me?