Objective: Compare execution times of the brute force and the divide-and-conquer

Question

Objective: Compare execution times of the brute force and the divide-and-conquer algorithms when solving the maximum subarray problem for arrays of different sizes. The arrays to be analyzed shall be the same for each algorithm, to make a valid comparison. Assignment: In your program, include a provision to generate arrays of varying sizes. Populate the arrays with integers, using a random number generator function (a library function is fine). Make a copy of this input array so that the same values w II be used in both algorithms. Use a timing function to measure the execution time for each algorithm used to analyze the input arrays. Test your algorithms using arrays of size: 10, 10C, and 1000 elements. Record the execution times and summarize the execution times in a table, ensuring that you provide time units for the execution times, i.e. seconds, milliseconds, clock cycles, etc. Generate a short summary of your experimental observations and based on your results, provide a commentary on when you would use each algorithm. (You may want to conduct more experiments to refine your recommendation.)

Explanation / Answer

#include <stdio.h>
#include <time.h>

// A function that terminates when enter key is pressed
void fun()
{
printf("fun() starts ");
printf("Press enter to stop fun ");
while(1)
{
if (getchar())
break;
}
printf("fun() ends ");
}

// The main program calls fun() and measures time taken by fun()
int main()
{
// Calculate the time taken by fun()
clock_t t;
t = clock();
fun();
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds

printf("fun() took %f seconds to execute ", time_taken);
return 0;
}

output:

Array of 10 is:

here i have used brute force algorithm- sequential search

and divide n conquer - binary search

here you can see that divide n conquer algorithm takes more time than brute force algorithm

Divide and conquer is a powerful tool for solving conceptually difficult problems, such as the classic Tower of Hanoi puzzle

Divide and conquer is a powerful tool for solving difficult problems, faster than brute-force algorithm because divide and conquer works by splitting up the original problem into smaller subproblems n then solves the smaller subproblems, these solutions reduce the total amount of work to do with respect to solving the original problem so yields Algorithm efficiency and Parallelism.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

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