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

Determine yiq colour model, Determine YIQ Colour Model Whereas an RGB m...

Determine YIQ Colour Model Whereas an RGB monitor requires separate signals for the red, green, and blue components of an image, a television monitor uses a single composite si

Explain b tree (binary tree), B Tree Unlike a binary-tree, every node o...

B Tree Unlike a binary-tree, every node of a B-tree may have a variable number of keys and children. The keys are stored in non-decreasing order. Every key has an associated ch

Explain linked list and its types, Data Structure and Algorithm 1. Exp...

Data Structure and Algorithm 1. Explain linked list and its types. How do you represent linked list in memory? 2. List and elucidate the types of binary tree. 3. Descr

Search on a hashed file, Write a program to simulate searching over a hashe...

Write a program to simulate searching over a hashed file, with different assumptions for the sizeof file pages.Write a program to perform equality search operations on the hashed f

Discrete time simulation of a queue, In this project you will write a progr...

In this project you will write a program to produce a discrete time simulation of a queue as shown in Fig. 1. Time is slotted on the input and the output. Each input packet follows

Explain arrays, Arrays :- To execute a stack we need a variable called top,...

Arrays :- To execute a stack we need a variable called top, that holds the index of the top element of stack and an array to hold the part of the stack.

Binary search tree, A binary search tree (BST), which may sometimes also be...

A binary search tree (BST), which may sometimes also be named a sorted or ordered binary tree, is an edge based binary tree data structure which has the following functionalities:

Explain the halting problem, Explain the halting problem Given a comput...

Explain the halting problem Given a computer program and an input to it, verify whether the program will halt on that input or continue working indefinitely on it.

Array, how to define the size of array

how to define the size of array

Find longest repeat prefix of string - linear time algorithm, 1. A string s...

1. A string s is said to be periodic with a period α, if s is α k for some k > 2. (Note that α k is the string formed by concatenating k times.) A DNA sequence s is called a tand

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