// Big-O Practice 02.cpp : Defines the entry point for the console application. //

// use system clock to compute Big-O

#include "stdafx.h" #include #include #include #include #include using namespace std;

void genData(int *data, int n) { // generate a random data set of size n for(int i = 0; i < n; i++) { data[i] = rand(); // rand is a standard lib function and generates a number between 0 and 32768 } }

void insertion_sort(int data[], int len) { // general insertion sort which uses increments you supply // can be used to perform Sedgewick, Hibbard, 531 and Shell sorts (or with any increments) // data[] this is the data to sort // len number of elements in data to sort int i, j, temp; for( i = 1; i < len; i++) { temp = data[i]; for( j = i; j >=1 && temp < data[j - 1]; j-=1) { data[j] = data[ j - 1]; } data[j] = temp; } return; }

int _tmain(int argc, _TCHAR* argv[]) { int *data; // hold the data generated by genData int N[] = {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192}; // N is the number of items to sort

int ncount = sizeof(N)/sizeof(int); // ncount is how many items are in N

// open a file that can be read by Excel ofstream f; f.open("graph_times.csv", ios::out); // this file will be created in the same directory as your source code for this project if(f.fail()) { cout << "graph file did not open" << endl; }

f << "N" << "," << "N" <<"," << "N*N" << "," << "counter" << endl; // write column headings

clock_t start_time, stop_time; // holds time data from system clock

for(int i = 0; i < ncount; i++) { data = new int[N[i]]; // allocate space for the data int *temp = new int[N[i]]; // temp array to hold data genData(data, N[i]); // generate a data set of size N[i] and put it in data for(int j = 0; j < N[i]; j++)temp[j] = data[j]; // copy data into temp array for reuse

start_time = clock(); double t; int loop = 0; while ( true ) { // loop until the time is > 0 insertion_sort(data, N[i]); // sort the data t = double(clock() - start_time)/CLOCKS_PER_SEC; for(int j = 0; j < N[i]; j++)data[j] = temp[j]; // copy temp into data loop++; if(t > 0)break; } double sec = t / double(loop); // convert the time value to seconds - divide by loop to get the actual time

cout << N[i] << " " << sec << endl; // write N and time to screen f << N[i] << "," << N[i] <<"," << N[i]*N[i] << "," << sec << endl; // write N and time to Excel file for graphing delete [ ]data; delete [] temp; }

f.close(); // close the graph file system("pause"); // don't erase the screen so you can see what was written (press enter key to continue) return 0; }

What is the big O notation for tmain?