Tag: data structures

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…