Tradeoff between space and time complexity, Data Structure & Algorithms

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.

Posted Date: 4/4/2013 5:40:47 AM | Location : United States







Related Discussions:- Tradeoff between space and time complexity, Assignment Help, Ask Question on Tradeoff between space and time complexity, Get Answer, Expert's Help, Tradeoff between space and time complexity Discussions

Write discussion on Tradeoff between space and time complexity
Your posts are moderated
Related Questions
What values are automatically assigned to those array elements which are not explicitly initialized? Garbage values are automatically assigned to those array elements that

Enumerate about the carrier set members Ruby is written in C, so carrier set members (which is, individual symbols) are implemented as fixed-size arrays of characters (which is

the deference between insertion,selection and bubble sort

H o w can you r ot a t e a B i n a r y Tr e e? E x pl a i n r i g h t a n d l eft r ot a tion s by taking an e x a mpl e.   If after

Explain divide and conquer algorithms  Divide  and  conquer  is  probably  the  best  known  general  algorithm  design  method.  It   work according to the following general p

In the present scenario of global warming, the computer hard ware and software are also contributing for the increase in the temperature in the environment and contributing for the

/* The program accepts matrix like input & prints the 3-tuple representation of it*/ #include void main() { int a[5][5],rows,columns,i,j; printf("enter the order of

Q. Explain the term hashing? Explain any five well known hash functions.                         Ans: Hashing method provides us the direct access of record from the f

i need the full concept of it... please can anyone provide

Write a program to simulate searching over a hashed file, with different assumptions for the sizeof file pages.Write a program to perform equality search operations on the hashed f