Abstraction (ADT) | Implementation (DS) |

List | Dinamic Array Linked List |

Queue | Linked List based Queue Array based Queue Stack based Queue |

Map | Tree Map Hash Map / Hash Table |

Vehicle | Golf Cart Bicycle Smart Car |

Constant Time: | O(1) |

Logarithmic Time: | O(log(n)) |

Linear Time: | O(n) |

Linearithmic Time: | O((n)log(n)) |

Quadratic Time: | O(n^2) |

Cubic Time: | O(n^3) |

Exponential time: | O(b^n), b >1 |

Factorial Time: | O(n!) |

O(n + c) | = | O(n) |

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

a := 1 | i := 0 |

b := 2 | While i < 11 do |

c := a + 5\*b | i = i + 1 |

``` :0 While i < n Do i = i + 1 ``` | ``` :0 While i < n Do i = i + 3 ``` |

f(n) = n O(f(n)) = O(n) | f(n) = n/3 0(f(n)) = O(n) |