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
Ordinary variable An ordinary variable of a easy data type can store a one element only

extra key inserted at end of array is called

how we can convert a graph into tree

Q. Explain Dijkstra's algorithm for finding the shortest path in the graph given to us.  Ans: The Dijkstra's algorithm: This is a problem which is concerned with finding

hello, i need help in data mining assignment using sas em and crisp-dm

Q. Describe the representations of graph. Represent the graph which is given to us using any two methods Ans: The different ways by which we can represent graphs are:

Ask question #sdgsdgsdginimum 100 words accepted#

What is Space complexity of an algorithm? Explain.

Your first task will be to come up with an appropriate data structure for representing numbers of arbitrary potential length in base 215. You will have to deal with large negative

HOW LINKED LIST HEADER WORKS? HOW TO INSERT AND DELETE ELEMENTS IN LINKED LIST?