CS61B: Data Structures and Advanced Programming

Lecture Notes for Algorithmic Analysis I && Data Structures


-1 representation is all ones


x << n is x . 2 power n

x >> n is x / 2 power n rounded down 11111 >> 1 equals 11111 i.e -1/2 = -0.5 is -1 since -0.5 is negative and rounded down giving -1

(x >> 3) & ((1<<5)-1) = 5 bit integer bits 3-7 of x


Program run time is a function of the size of input data

do this for n=1,2,4,16,32,64,1024,2(pow 20)
O(16lgn)
o(sqrt(n))
o(n)
o(nlgn)
o(npow2)
o(npow3)
o(2pow2n)


The O notation is good to tell us how fast the program runs

e.g a single for loop is o(N) since it would take N time in worst case
But the O notation is ambiguous since O is Upper bound so the same for loop is also O(N pow2) so Big O Notation is not good.

But it is good to say Theta Notation than O since theta is the worst case

2 nested for loop are O(nsq)
recusion is O(2(pow n))