Tradeoff between space and time complexity, Data Structure & Algorithms

Assignment Help:

We might sometimes seek a tradeoff among space & time complexity. For instance, we may have to select a data structure which requires a lot of storage to reduce the computation time. Thus, the programmer has to make a judicious choice from an informed point of view. The programmer have to have some verifiable basis based on which a data structure or algorithm can be selected Complexity analysis provides such a basis.

We will learn regarding various techniques to bind the complexity function. Actually, our goal is not to count the exact number of steps of a program or the exact amount of time needed for executing an algorithm. In theoretical analysis of algorithms, this is common to estimate their complexity in asymptotic sense that means to estimate the complexity function for reasonably large length of input 'n'. Omega notation ?, big O notation, and theta notation Θ are utilized for this purpose. To measure the performance of an algorithm underlying the computer program, our approach would be depending on a concept called as asymptotic measure of complexity of algorithm. There are notations such as big O, Θ, ? for asymptotic measure of growth functions of algorithms. The most common is big-O notation. The asymptotic analysis of algorithms is frequently used since time taken to execute an algorithm varies along with the input 'n' and other factors that might differ from computer to computer and from run to run. The essences of these asymptotic notations are to bind the growth function of time complexity along with a function for sufficiently large input.


Related Discussions:- Tradeoff between space and time complexity

Kruskal algorithm for minimum spanning, Implementations of Kruskal's algori...

Implementations of Kruskal's algorithm for Minimum Spanning Tree. You are implementing Kruskal's algorithm here. Please implement the array-based Union-Find data structure.

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

Draw the process flow diagram, Draw the process flow diagram: Anand   ...

Draw the process flow diagram: Anand   Dairy (AD) sources 150,000 litres of milk daily from large number of local villagers .The milk is collected from 4:00 AM to 6:00 am and

Explain dijkstra''s algorithm, Explain Dijkstra's algorithm Dijkstra's ...

Explain Dijkstra's algorithm Dijkstra's algorithm: This problem is concerned with finding the least cost path from an originating node in a weighted graph to a destination node

Finite automata, find the grammar of regular expression of (a/?)(a/b)?

find the grammar of regular expression of (a/?)(a/b)?

File organization, Define File organization''s and it''s types

Define File organization''s and it''s types

Rooted tree, It does not have any cycles (circuits, or closed paths), which...

It does not have any cycles (circuits, or closed paths), which would imply the existence of more than one path among two nodes. It is the most general kind of tree, and might be co

Definition of algorithm, Definition of Algorithm Algorithm must have th...

Definition of Algorithm Algorithm must have the following five characteristic features: 1.      Input 2.      Output 3.      Definiteness 4.      Effectiveness 5

Multikey file organization, what are the applications of multikey file orga...

what are the applications of multikey file organization?

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