October 28th, 2015

Classroom Salon: Video 2.3: Order of Growth

Visit edmodo.com:
1.
Quiz
How many accesses does the following code fragment make as a function of N?
(Assume the compiler does not optimize away any array accesses int eh innermost loop)

int sum = 0;
for (int i = 0; i < N ; i++ )
---> for (int j = i + 1; j < N ; j++ ) 
--------> for (int k = 1; k < N ; k = k*2 )
------------> if ( a[i] + a[j] >= a[k]) sum++;

~3N^2
~(3/2)N^2 lgN
~(3/2)N^3
~3N^3

2.
Proposition: Binary search uses at most 1 + lgN compares to search in a sorted array of size N.
Def. T(N) = # compares to binary search in a sorted subarray of size <= N. Binary search recurrence. T(N) <= T(N/2) + 1 for N>1, with T(1) = 1
Give an example to show
T(N) <= T(N/2) + 1 for N>1, with T(1) = 1
Show how 1 + 1 + … + 1 become 1 + lg N

3.
Write a program, YI_Better3Sum.java, so its order of growth is N^2 log N

4.
Create a table to compare the execution run time from the original 3-Sum and the Better3Sum.