Data Structure (0) - Abstract Data Type and Big O

Abstract Data Type

What is a Data Structure?

A data structure is a way of organizing data so it can be used effectively.

Why Data Structure?

  • Essential ingredients in creating fast and powerful algorithm.
  • Help to manage and organize data.
  • Make code cleaner and easier to understand

Abstract Data Type

  • ADT is an abstraction of a data structure which provides only the interface to a data structure must adhere to.
  • ADT does not give any specific details about how something should be implemented

Example

Abstraction(ADT) Implementation(DS)
List Dynamic Array, Linked List
Map Tree Map, Hash Map
Vehicle Bicycle, Smart Car

Computational Complexity Analysis

Complexity Analysis

  • How many time does this algorithm need to finish?
  • How many space does this algorithm need for its computation?

Big-O Notation

Big-O gives the upper bound of the complexity of worst case, helping to quantify performance as the input sie becomes arbitrarily large.

n = The size of the input

Complexity Term

Complexity ordered in from smallest to largest

Term Big-O Notation
Constant $ O(1) $
Logarithmic $ O(log(n)) $
Linear $ O(n) $
Linearithmic $ O(nlog(n)) $
Quadric $ O(n^2) $
Exponential $ O(b^3), b > 1 $
Factorial $ O(n!) $

Example

Let $f$ be a function that describes the running the time of a particular algorithm for an input of size n:

$ f(n) = 7log(n)^3+15n^2+2n^3 + 8 $

Complexity analysis only cares about the worst case, the complexity of $f(n)$ will be

$O(f(n)) = O(n^3)$

More Examples

The following run in linear time: $O(n)$

$f(n) = n$

i := 0
While i < n Do
    i = i + 1

$f(n) = n/3$

i := 0
While i < n Do
    i = i + 3

The following run in Quadric time: $O(n^2)$

$f(n) = n*n = n^2$

For (i:=0; i < n; i = i + 1)
    For (j:=0; j < n; j = j + 1)

Even change j:=0 to j:=n, the complexity still remains. If i=0, we do n work, If i=1 we do n-1 work, etc...

For (i:=0; i < n; i = i + 1)
    For (j:=n; j < n; j = j + 1)

So the question becomes what is: $(n) + (n-1) + (n-2) + (n-3)+...+3+2+1 $

Turns out to be $O(n(n+1)/2) = O(n^2/2 + n/2) = O(n^2)$

Again, complexity analysis only cares about the worst case, so the complexity would be $O(n^2)$

This also a $O(n^2)$ example. $O(f(n)) = O(n*(3n+2n)) = O(n^2)$

i := 0
While i < n Do
    j = 0
    While j < 3*n Do
        j = j + 1
    j = 0
    While j < 2*n Do
        j = j + 1
    i = i + 1

Suppose we have a sorted array and we want to find the index of a particular value in the array, if it exists.

Time complexity below is $O(log(n))$.

low := 0
high := n - 1
While low <= high Do

    mid := (low + high) / 2

    If array[mid] == value: return mid
    Else If array[mid] < value: low = mid + 1
    Else If array[mid] > value: high = mid - 1

return -1
Tags:
# data structure
# computer science