Data structures an introduction

Data structure: Way of organizing data so we can efficiently use it.
Essential ingredients in creating fast and powerful algorithms.
Help to manage and organize data.
makes code cleaner and easier to understand.

Abstract data type: Is an abstraction of a data structure which provides only the interface to which a data structure must adhere to. Interface will not give any specifics to how something should be implemented or in what programming language.

ADT – Implementation(DS)
List – Dynamic Array, Linked list.
Queue – Linked List Based queue, Array based queue, Stack base queue
Map – Tree map, Hash map, Hash table

Computational complexity analysis:
How much time does this algorithm needs to finish the computation?
How much space does this algoritm needs to finish the computation?

Big data
Omega meta data

Big-O notation: Upper bound complexity of the worst case irrespective of the size of data(small data set or large data set)
n – The size of the input
Complexities ordered in from the smallest to largest.
Constant Time : O(1)
Logarithmic Time : O(log(n))
Linear time : O(n)
Linearithmic Time : O(nlog(n))
Quadric Time : O(nsquared)
Cubic Time : O(ncube)
Exponential Time : O(bpowern), b>1
Factorial Time : O(n!)

O(n + c) = O(n)
O(cn) = O(n), c > 0

f(n) = 7 log(n)3 + 15n2 + 2n3 + 8

O(f(n)) = O(n3) as n3 is the biggest value.

Read More…

About the Author


21 years of experience in various layers of software. Primarily experienced in system side software design and development on server management software. Interested in linux development in x86 and arm architecture.