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

How will you represent a max-heap sequentially, How will you represent a ma...

How will you represent a max-heap sequentially? Max heap, also known as the descending heap, of size n is an almost complete binary tree of n nodes such that the content of eve

Delete a given node from a doubly linked list, Algorithm to Delete a given ...

Algorithm to Delete a given node from a doubly linked list Delete a Node from Double Linked List DELETEDBL(INFO, FORW, BACK, START, AVAIL,LOC) 1. [Delete Node] Set FOR

The various ways in which lc code can be accessed, Problem Your LC code...

Problem Your LC code is stored in a memory location as shown and the variable name is LC LC Memory address Content(LC code)

Explain circular queues, Circular Queues:- A more efficient queue repre...

Circular Queues:- A more efficient queue representation is get by regarding the array Q(1:n) as circular. It becomes more convenient to declare the array as Q(O: n-1), when re

Data structures, Aa) Come up with an ERD from the following scenario, clear...

Aa) Come up with an ERD from the following scenario, clearly stating all entities, attributes, relationships before final sketch of the ERD: [50 m

Need it urgently, Write an assembly program to separate the number of posit...

Write an assembly program to separate the number of positive numbers and negative numbers from a given series of signed numbers.

Heap sort, We will start by defining a new structure called Heap. Figure 3 ...

We will start by defining a new structure called Heap. Figure 3 illustrates a Binary tree. Figure: A Binary Tree A complete binary tree is said to assure the 'heap con

Various passes of bubble sort, Q. Show the various passes of bubble sort on...

Q. Show the various passes of bubble sort on the unsorted given list 11, 15, 2, 13, 6 Ans: The given data is as follows:- Pass 1:- 11 15 2 13

Advanced trees, Linked list representations contain great advantages of fle...

Linked list representations contain great advantages of flexibility on the contiguous representation of data structures. However, they contain few disadvantages also. Data structur

State the painter algorithm, Painter's Algorithm As the name suggests, ...

Painter's Algorithm As the name suggests, the algorithm follows the standard practice of a painter, who would paint the background (such as a backdrop) first, then the major d

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages