Determination of time complexity, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Determination of time complexity

What is diffuse illumination, Diffuse Illumination Diffuse illuminatio...

Diffuse Illumination Diffuse illumination means light that comes from all directions not from one particular source. Think about the light of a grey cloudy day as compared to

#title.structured programming, what do you understand by structured program...

what do you understand by structured programming?explain with eg. top down and bottem up programming technique

Explain dijkstra''s algorithm, Explain Dijkstra's algorithm Dijkstra's ...

Explain Dijkstra's algorithm Dijkstra's algorithm: This problem is concerned with finding the least cost path from an originating node in a weighted graph to a destination node

Deletion of a node from a binary search tree, The algorithm to delete any n...

The algorithm to delete any node having key from a binary search tree is not simple where as several cases has to be considered. If the node to be deleted contains no sons,

Stack, write pseudocode to implement a queue with two stacks

write pseudocode to implement a queue with two stacks

Define the term ''complexity of an algorithm, Define the term 'complexity o...

Define the term 'complexity of an algorithm; Complexity of an algorithm is the calculate of analysis of algorithm. Analyzing an algorithm means predicting the resources that th

Data mining assignment, The assignment aims at consolidating your knowledge...

The assignment aims at consolidating your knowledge on data mining techniques and developing practical skills through solving a problem of transcription factor binding sites recogn

How many nodes in a tree have no ancestor, How many nodes in a tree have no...

How many nodes in a tree have no ancestors 1 node in atree have no ancestors.

All pairs shortest paths algorithm, In the last section, we discussed regar...

In the last section, we discussed regarding shortest path algorithm that starts with a single source and determines shortest path to all vertices in the graph. In this section, we

Properties of red- black tree, Any Binary search tree has to contain follow...

Any Binary search tree has to contain following properties to be called as a red- black tree. 1. Each node of a tree must be either red or black. 2. The root node is always b

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd