CSE 373 Lecture Notes - Lecture 3: Binary Search Tree, Avl Tree, Asymptotic Analysis
17 May 2018
School
Department
Course
Professor
CSE 373 Lecture 3
More on asymptotic analysis
- N-not (n0) is for the case when n is less than 1
- Big Oh – family/set of all functions that are dominated by f(n)
- F(n) is less than g(n) = f(n) is dominated by g(n) → f(n) is contained inside O(g(n))
o Symbol E = “contained within the set of”
- Big Omega – represents functions that dominate f(n)
DATA STRUCTURE: Trees
- Binary search tree – contains comparable items; all children in left contain smaller data,
all children in right contain larger data
o Implementing a dictionary
o Runtime in terms of height (h)
▪ Get() – O(h)
