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

Compound interest, Write the algorithm for compound interest

Write the algorithm for compound interest

Frequency count, what is frequency count with examble

what is frequency count with examble

Addressing modes, Compare zero-address, one-address, two-address, and three...

Compare zero-address, one-address, two-address, and three-address machines by writing programs to compute: Y = (A – B X C) / (D + E X F) for each of the four machines. The inst

Implementation of stack, Implementation of Stack :- Stacks can be execu...

Implementation of Stack :- Stacks can be executed in the 2 ways: a)  Arrays b)  Linked List

#input restricted DEQUE, #why all the 4 operations i.e. insertion n del...

#why all the 4 operations i.e. insertion n deletion from rear end and front end is valid in input restricted DEQUE

Complexity of quick sort, Q. What do you mean by the best case complexity o...

Q. What do you mean by the best case complexity of quick sort and outline why it is so. How would its worst case behaviour arise?

Row major storage, Q. Take an array A[20, 10] of your own. Suppose 4 words ...

Q. Take an array A[20, 10] of your own. Suppose 4 words per memory cell and the base address of array A is 100. Find the address of A[11, 5] supposed row major storage.

Effective way of storing two symmetric matrices, Explain an efficient and e...

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

Efficiency of binary search, Each of the comparison in the binary search de...

Each of the comparison in the binary search decrease the number of possible candidates where the key value can be searched by a factor of 2 as the array is divided into two halves

Circular linked list, In a circular linked list There is no beginning a...

In a circular linked list There is no beginning and no end.

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