When are you justified in using an O(n^2) algorithm? (b) Exhaustive search is an

Question

When are you justified in using an O(n^2) algorithm? (b) Exhaustive search is an example of which type of strategy? Give an example where you might use it (c) What is a Divide-and-Conquer strategy? Give an example. (d) What is a Greedy algorithm? Briefly explain how it works and give an example. (e) A Decrease-by-One strategy is one where the size of the problem to be solved is steadily decreased by one element on each iteration. "Insertion sort is a Decrease-by-One algorithm". Given the definition and your knowledge of insertion sort, is this statement true? Explain your answer and clearly identify the features of insertion sort that are supporting your argument.

Explanation / Answer

a)In case of Sorting algorithm can justify complexity measure O(n2)

Because the outer loop iterates n times and the inner loop iterates n times as well for double-counting.

The inner loop iterates n times that means (n-1) + (n-2) + (n-3) + ... + 1 times.

The outer loop iterates n times.

So complexity will be n * (the sum of the numbers 1 to n)

Count for the n number of elements to be sorted by adding the work done through each and every iteration from the loop initialization to get the first iteration is being done n , the second n - 1, the third n - 2, etc., since the ith iteration of the top-level inner loop is doing n - i iterations.

The inner loop runs O(n) work on each iteration where the outer loop runs for O(n) iterations as well, so the total complexity is O(n2).

b) Exhaustive search is also called brute force search which is offering a best strategy to explore the entire search time and space, testing every possible solution.

Exhaustive search can be used to reduce the search space because randomization can be enforced to upgrade the running times. Exhaustive searches is a backtracking algorithms but all backtracking algorithms are not exhaustive. The algorithm is working for searching every possible way to get a solution merging with to reduce the number of items to be searched for.

For both Traveling Salesman and Knapsack problems are the example of exhaustive search which have an exponential time complexity.

These are NP-hard problems that means not a polynomial-time algorithm.

Traveling Salesman Problem (TSP)

•          Find the shortest route through a set of n cities which visits each city exactly once before returning back to that very city from where it is started

•          It is conveniently designed by a weighted graph where vertices are cities and edges are weighted as distances.

Exhaustive search for an optimal solution applying all possible permutations where the time of this exhaustive searching approach complexity will be O(n!), Since considering (n - 1)! different permutation where each permutation runs O (n) time to evaluate.

c) Divide and Conquer algorithm design strategy:

1. Firstly Divide instance of problem into two or more smaller groups

2. Solving the smaller instances recursively

3. Obtaining solution to original (larger) instance

Divide-and-conquer algorithm example :

The Binary Search is a divide and conquer algorithm:

For analyzing the binary search algorithm it is required to recall that each comparison excludes about half of the remaining items for next iteration.. So the maximum number of comparisons to check the entire list:

Starting with n items, about n/2 items will be left after the first comparison. After the second comparison it will be n/4 items will be left , next left n/8,n/16,......up to. n/2i

1) To solve a problem by solving a smaller sub problem using Divide

2) Using the solution for generating bigger problem solution by Conquer method

d) A greedy algorithm is an algorithmic prototype which follows examining for creating the locally optimized solution at each stage for finding a global solution.

A greedy algorithm, always makes the choice to get optimal solution.

Working principle:

A Greedy algorithm incorporates a greedy approach at each step to allow that the function is being optimized. As it is used to compute the optimal solution so that it never and reverses the optimized decision

e) Insertion sort breaks the set of elements for sorting into two subsets:

1) already sorted,

2) unsorted.

Elements of the subset 'unsorted' are moved to the 'already sorted' set one-by-one. As the size of the problem is the size of the 'unsorted' set, it is decreased by one . The algorithm can be considered as 'decrease-by-one'.

Algorithm to sort n elements:

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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