COMPSCI 61B Lecture Notes - Lecture 17: Time Complexity, Linked List, Binary Search Algorithm
Document Summary
Performance of operations on spindly trees can be just as bad as a linked list. A wost case (spindly tree) has a height that grows exactly linearly - (n) All bsts have a height that grows linearly or better - o(n) All bsts have a heigh that grows quadratically or better - o(n squared: saying that the worst case has an order of growth n is more informative than saying the height is o(n) Big o is not mathematically the same thing as worst case . Bst heights are o(n squared) but are not quadratic in the worst case. But big o often used as shorthand for worst case (in the real world) Allows us to make simple blanket statements. Can say binary search is o(log n) instead of binary search is (log n) in the worst case. Sometimes don"t know the exact runtime, so use o to give an upper bound.
