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

Define tree ?, A tree is a non-empty set one component of which is designat...

A tree is a non-empty set one component of which is designated the root of the tree while the remaining components are partitioned into non-empty groups each of which is a subtree

General Tree, How to create an General Tree and how to search general tree?...

How to create an General Tree and how to search general tree?

Insertion of a node into an avl tree, Initially Nodes are inserted in an AV...

Initially Nodes are inserted in an AVL tree in the same manner as an ordinary binary search tree. Though, the insertion algorithm for any AVL tree travels back along with the pa

Define binary tree, Define Binary Tree  A binary tree T is explained as...

Define Binary Tree  A binary tree T is explained as a finite set of nodes that is either empty or having of root and two disjoint binary trees TL, and TR known as, respectively

Postfix expression algorithm, Write an algorithm to calculate a postfix exp...

Write an algorithm to calculate a postfix expression.  Execute your algorithm using the given postfix expression as your input : a b + c d +*f ↑ . T o evaluate a postfix expr

Define stack lifo, A stack is a last in, first out (LIFO) abstract data typ...

A stack is a last in, first out (LIFO) abstract data type and sequential data structure. A stack may have any abstract data type as a component, but is characterized by two fundame

Write an algorithm to measure daily temperatures, A geography class decide ...

A geography class decide to measure daily temperatures and hours of sunshine each day over a 12 month period (365 days) Write an algorithm, using a flowchart that inputs tempera

Efficient way of storing two symmetric matrices, Explain an efficient way o...

Explain an efficient way of storing two symmetric matrices of the same order in memory. A n-square matrix array is said to be symmetric if a[j][k]=a[k][j] for all j and k. For

Primitive data structure, Primitive Data Structure These are the basic ...

Primitive Data Structure These are the basic structure and are directly operated upon by the machine instructions. These in general have dissimilar representations on different

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