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))
