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

Array, how to define the size of array

how to define the size of array

Function performs multiplication of two numbers, You need to write a functi...

You need to write a function that performs multiplication of two numbers in your data structure. Again, remember how you multiply numbers in base 10 and you should be fine. Multipl

Types of tree ?, Binary: Each node has one, zero, or two children. This ...

Binary: Each node has one, zero, or two children. This assertion creates many tree operations efficient and simple. Binary Search : A binary tree where each and every left

Accept a file and form a binary tree - huffman encoding, Huffman Encoding i...

Huffman Encoding is one of the very simple algorithms to compress data. Even though it is very old and simple , it is still widely used (eg : in few stages of JPEG, MPEG etc). In t

Implementation of circular queues, One of the main problems with the linear...

One of the main problems with the linear queue is the lack of appropriate utilization of space. Assume that the queue can store 100 elements & the complete queue is full. Thus, it

Total impedent of the circuit, an electrical student designed a circuit in...

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Hash table, Q. Make the 11 item hash table resulting from hashing the given...

Q. Make the 11 item hash table resulting from hashing the given keys: 12, 44, 13, 88, 23, 94, 11, 39, 20, 16 and 5 by making use of the hash function h(i) = (2i+5) mod 11.

Header linked list, creation,insertion,deletion of header linked list using...

creation,insertion,deletion of header linked list using c.

Preorder traversal of a binary tree, Preorder traversal of a binary tree ...

Preorder traversal of a binary tree struct NODE { struct NODE *left; int value;     /* can take any data type */ struct NODE *right; };   preorder(struct N

Hashing and hash functions, Q. Describe the term hashing. Explain any two u...

Q. Describe the term hashing. Explain any two usually used hash functions. Explain one method of collision resolution.

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