1. Prove that the function T( n ) = 14n⁴+3n³+21n - 50 is in O( n⁴ )

2. Prove that the function T( n ) = n³ + 14n + 7 is in O( n³ )

3. Use Induction to prove that:

n
summation of 2i	= 2n+1 - 1 for all n > 0
i = 0

4. Consider each of the following programs. Determine their expected running times, T( n ), using big-O notation. Note the table below which specifies running times for various functions called by the programs.

Function Name	Running Time, T( n )
constantTimeFunction( n )	T( n ) = O( 1 )
linearTimeFunction( n )	T( n ) = O( n )
quadraticTimeFunction( n )	T( n ) = O( n2 )
cubicTimeFunction( n )	T( n ) = O( n3 )

Program 1	Program 2
constantTimeFunction( n ); linearTimeFunction( n ); constantTimeFunction( n ); quadraticTimeFunction( n );	for (i=0; i quadraticTimeFunction( n ); cubicTimeFunction( n ); constantTimeFunction( n ); }
O( 1 ) O( n ) O( n2 )O( n3 )O( n4 )O( n5 )	O( 1 ) O( n ) O( n2 )O( n3 )O( n4 )O( n5 )
Program 3	Program 4
for (i=0; ifor (j=0; j linearTimeFunction( n ); linearTimeFunction( n ); constantTimeFunction( n ); } }	for (i=0;i<9*n;++i) { quadraticTimeFunction( n ); for (j=0;j cubicTimeFunction( n ); } linearTimeFunction( n ); }
O( 1 ) O( n )O( n2)O( n3 )O( n4 )O( n5 )	O( 1 ) O( n ) O( n2 )O( n3 )O( n4 )O( n5 )

5. Download the SubSequence program for your development environment (VS.Net2012 XCode7). Unzip and then run the program on a number of data sets of varying sizes (small, medium and large), completing the table shown below. In addition, please attempt to determine whether, for the same data set, the running time changes based on different order of input of the same data.

	Total Number Of Operations Performed By:
Sequence Data entered	O( n ) Algorithm	O( n2 ) Algorithm	O( n3 ) Algorithm

Will the same sequence of data have a different running time when the order of the input changes? yes no