data
information systematic data
two important things about data types
1)defines a certain domain of values
2)define operations allowed on these values
Abstact data types
Ex stack ADT
operations
initilize()
Push()
isEmpty()
Pop()
isFull()
stack ADT arrya and linkedlists
types of data structures
1)linear data structures
2)non-lineat data structures
1)LINEAR DATA STRUCTURES
arrays
queue
stack
linked list
2)NON-LINEAR LINKED STRUCTURE
tree
graph
Static data structures
In these type of data structures that memory is allocated at compile thime
Therefore maximum size is fixed advantade fast access slower insertation and
deletion
Dynamic data structures
In these type of data structures that memoru is allocated at run time. THererfore
maximum size if flexible advantage faster insertion and deletion slower access
efficiency of data structure is always is terms of time and space
inserting an element at the beginning of the list is way faster in the linked list
than arrays
time complexity or running time
1)examine the exat running time
2)the runnlng time generally depends on the size of the input
growth rate of f(n)=5n*n+6n+12
n 5n*n 6n 12
1 21.74% 26.09% 52.17%
10 87.41% 10.49% 2.09%
100 98.07% 1.19% .02%
1000 99.88% .12% .0002%
the larger the value of n the sqared term consumes almost 99% of time
so we can neglect 6n +12 so f(n)=5n*n
the approximate measure of time complexity is called asymptotic complexity
BIG O NOTATION
g=big o noation us used to measure the performance of any algorithm by
providing the order of groth o fthe function
it gives the upper bounf on a function by which we can make sure that the
function will never grow faster than this upper bound
we want the approximate runtime of the operations performed on data
structures we are not interested in the exact runtime
if f(n) and g(n) are the two functions, then
f(n)=o(g(n))
if there exists constants c and n0 such that f(n)=<=c*g(n), for all n>=n0
this simply means that f(n) dies not grow faster than g(n)
