Time Complexity: Empirically test the assertion that the execution times of sele

Question

Time Complexity:

Empirically test the assertion that the execution times of selection sort, bubble sort, and insertion sort algorithms are in O(n2). To do this, implement and execute each algorithm using vectors of different sizes and record the execution times. If an algorithm is indeed in O(n2), there must exist a constant c such that for any n the execution time is c * n2. Implement each algorithm and first make sure the corresponding program works correctly. Then for each n determine the execution time and the value of n2. Now working your way backward you could compute the value of c by dividing the execution time by n2. If the values of c are roughly equal for each n then the algorithm is indeed in O(n2).

You could use the time command to measure how much time your program takes for a given value of n. Run your program as follows:

where the user enters n and the program generates a vector (of size n) of random integers in the range [0-1,000,000). The program then proceeds to sort and output the numbers into output file. It is important to make sure that n is a user input and the above output redirection is used. Otherwise, the typescript of the sample runs would get unmanageably too large! After the program terminates, the time command prints real, user, and system times. You are interested in user time. Type

to learn more about this command.
Run each program 10 times starting with n = 1,000 and incrementing n each time by 1,000.
Hand in a printout of each program, the typescript of all 10 runs for each program, and the following completed table for each program/algorithm:

Use STL vector v to implement all three functions where n is the size of the vector. The algorithms for the functions follow:

n n2 Exec Time (sec) c = Time / n2 1,000 1,000,000 ... ... 2,000 4,000,000 ... ... ... ... ... ... 10,000 100,000,000 ... ...

Explanation / Answer

#include #include #include using namespace std; const int M = 5, N = 4; class Point { int x, y; public: Point(int a, int b) : x(a), y(b) {} int getX() { return x;} int getY() { return y;} }; bool isFree(int x, int y) { if(x == 0 && y == 1) return false; if(x == M-1 && y == N-1) return false; return true; } bool getPath(int x, int y, vector& path, map& pMap) { bool go = false; Point *p = new Point(x,y); if(x == 0 && y == 0) return true; if(x >= 1 && !pMap[p] && isFree(x,y)) go = getPath(x-1,y, path, pMap); if(!go && y >= 1 && !pMap[p] && isFree(x,y)) go = getPath(x,y-1, path, pMap); if(go && isFree(x,y)) { path.push_back(p); pMap.insert(make_pair(p, true)); } return go; } int main() { vector path; map pMap; getPath(M, N, path, pMap); for(int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.