Big-O Notation (Time Complexity)

ADTs

Circular Array Queue

Level Order Traversal (using queue)

Graph

Tree Traversals (Inorder, Preorder and Postorder)

Week1-Analysis of algorithms

An algorithm is a step-by-step procedure for solving a problem in a finite amount of time.

• Running Time
  • running time typically grows with input size.
  • average time often difficult to determine, so we focus on worst case running time.
• Empirical Analysis:
  • write and run program with inputs of varying size and composition, also plot the results.
  • but their on some limitations like same hardware and operating system must be used in order to compare two algorithms.
• Theoretical Analysis
  • Uses high-level description of the algorithm instead of implementation ("pseudocode")
  • Use characterises running time as a function of the input size, n

Week2

Week3-Binary Search Trees(BSTs)

<aside> 🧸 Binary search is is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.

</aside>

Binary search trees (BSTs) are able to be searched with a binary search, and are easy to maintain/modify.

Why BST?