Big-O

Does Big-O tell the whole story?
• Tx(n) = Ty(n) = O(lg n)

T1(n)=50+3n+(10+5+15)n = 50+33n
setup of algorithm -- takes 50 time units
read n elements into array -- 3 units/element
for i in 1..n loop
do operation1 on A[i] -- takes 10 units
do operation2 on A[i] -- takes 5 units
do operation3 on A[i] -- takes 15 units

T2(n)=200+3n+(10+5)n = 200+18n
setup of algorithm -- takes 200 time units
read n elements into array -- 3 units/element
for i in 1..n loop
do operation1 on A[i] -- takes 10 units
do operation2 on A[i] -- takes 5 units

Linear Search
• If data distributed randomly
– Average case:
• N/2 comparisons needed
– Best case:
• values is equal to first element tested
– Worst case:
• value not in list -> N comparisons needed
Linear Search is O(N)

Binary Search
• Can be performed on
– Sorted arrays
– Full and balanced BSTs
• Compares and cuts half the work
– We cut work in ½ each time
– How many times can we cut in half?
Binary Search is O(Log N)

Insertion to a Sorted Array
• Sorted Array
– Finding the right spot – O(Log N)
– Performing the shuffle – O(N)
– Performing the insertion - O(1)
Total work: O(Log N + N + 1) = O(N)

Insertion into a F&B BST
• Finding the right spot – O(Log N)
• Performing the insertion – O(1)
Total work: O(Log N + 1) = O(Log N)

Insertion Sort – O(N2)
• Assume you are sorting 250,000,000 item
N = 250,000,000 N^2 = 6.25 * 10^16
Assume you can do 1 operation/nanosecond
-> 6.25 * 10^7 seconds
= 1.98 years

Merge Sort – O(N * Log N)
• Assume you are sorting 250,000,000 item
N = 250,000,000
N*Log N = 250,000,000 * 28
Assume you can do 1 operation/nanosecond
-> 7.25 seconds