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

Define container in terms of object-oriented terms, Define container in te...

Define container in terms of  object-oriented terms A Container is a broad category whose instances are all more specific things; there is never anything which is just a Contai

Define data model, Define data model?  A data model is a collection of ...

Define data model?  A data model is a collection of conceptual tools for explaning data, data relationships, data semantics and consistency constraints.

Array, how to define the size of array

how to define the size of array

Just a quick couple questions, I was wanting to know where this web site wa...

I was wanting to know where this web site was created. My second question is,,, are the online tuters accredited teachers? If they are, are they only working for the website or ma

Functions for inserting and deleting at either of the end, Q. Develop a rep...

Q. Develop a representation for a list where insertions and deletions can be done at either end. Such a structure is known as a Deque (Double ended queue). Write functions for inse

Define queue fifo ?, A queue is a particular type of collection or abstract...

A queue is a particular type of collection or abstract data type in which the entities in the collection are went in order and the principal functions on the collection are the add

What is string, What is String Carrier set of the String ADT is the s...

What is String Carrier set of the String ADT is the set of all finite sequences of characters from some alphabet, including empty sequence (the empty string). Operations on s

State the term access restrictions - container, What is Access Restriction...

What is Access Restrictions Structured containers with access restrictions only allow clients to add, remove and examine elements at certain locations in their structure. For

Explain principle of optimality, Explain principle of Optimality It ind...

Explain principle of Optimality It indicates that an optimal solution to any instance of an optimization problem is composed of  optimal solutions to its subinstances.

Write procedure to the insert a node into the linked list, Q. Write a proce...

Q. Write a procedure to the insert a node into the linked list at a particular position and draw the same by taking an example?

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