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(n²). 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

#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

Linked list implementation of a dequeue, Double ended queues are implemente...

Double ended queues are implemented along doubly linked lists. A doubly link list can traverse in both of the directions as it contain two pointers namely left pointers and righ

Structures for complete undirected graphs, Q. Draw the structures of compl...

Q. Draw the structures of complete undirected graphs on one, two, three, four and five vertices also prove that the number of edges in an n vertex complete graph is n(n-1

How can the third dimension be displayed on the screen, How can the third d...

How can the third dimension be displayed on the screen The main problem in visualization is the display of three-dimensional objects and scenes on two-dimensional screens. How

Dgsd, Ask question #sdgsdgsdginimum 100 words accepted#

Ask question #sdgsdgsdginimum 100 words accepted#

Find strongly connected components - dfs, A striking application of DFS is ...

A striking application of DFS is determine a strongly connected component of a graph. Definition: For graph G = (V, E) , where V refer to the set of vertices and E refer to the

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

Best case, for i=1 to n if a[i}>7 for j=2 to n a[j]=a{j}+j for n=2 to n a...

for i=1 to n if a[i}>7 for j=2 to n a[j]=a{j}+j for n=2 to n a[k]=a[j]+i else if a[1]>4 && a[1] for 2 to a[1] a[j]= a{j]+5 else for 2to n a[j]=a[j]+i ..

One dimenjsional array, how do you declare char text[80]

how do you declare char text[80]

Define heap, HEAP A heap is described to be a binary tree with a key i...

HEAP A heap is described to be a binary tree with a key in every node, such that 1-All the leaves of the tree are on 2 adjacent levels. 2- All leaves on the lowest leve

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages