COMP 250 Lecture Notes - Lecture 21: Binary Search Tree, Binary Search Algorithm, Dynamic Array

• School: McGill University
• Department: Computer Science (Sci)
• Course: COMP 250
• Professor: Michael Langer

Document Summary

Bounds: best and worst case & o(), (), () Add, remove, find an element (double linked list) If the first thing selected is the right right spot. 2 n n n log n n log n n n log( n. These algorithms have these different complexity classes. " for some algorithms, the speedo of the algorithm depends on the input, so the best case can be quite different from the worst case. We"ve been talking about asymptotic bounds (like o()), which means that the algorithm runs no worse than ___ is the upperbound. It t(n) is o( g(n) ) t(n) is ( g(n) ) t(n) is ( g(n) ) t(n) c 2 g(n) The function grows no worse than some fixed constant c 2 times this other function g(n), where g(n) is simple (like n c 2, g(n) t(n) The time it takes the algorithm to run is minimum g(n) times some constant. or n.