Algorithms and asymptotic notations. I don\'t understand. Please help CS3343 Ana
ID: 3877560 • Letter: A
Question
Algorithms and asymptotic notations. I don't understand. Please help
Explanation / Answer
Asymptotic analysis of an algorithm refers to defining the mathematical boundation/framing of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case, and worst case scenario of an algorithm.
Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is concluded to work in a constant time. Other than the "input" all other factors are considered constant.
Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. For example, the running time of one operation is computed as f(n) and may be for another operation it is computed as g(n2). This means the first operation running time will increase linearly with the increase in n and the running time of the second operation will increase exponentially when n increases. Similarly, the running time of both operations will be nearly the same if n is significantly small.
Usually, the time required by an algorithm falls under three types
Worst Case Analysis :In the worst case analysis, we calculate upper bound on running time of an algorithm. We must know the case that causes maximum number of operations to be executed.. Therefore, the worst case time complexity of linear search would be (n).
Average Case Analysis :In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs. We must know (or predict) distribution of cases. For the linear search problem, let us assume that all cases are uniformly distributed (including the case of x not being present in array). So we sum all the cases and divide the sum by (n+1). Following is the value of average case time complexity
Best Case Analysis: In the best case analysis, we calculate lower bound on running time of an algorithm. We must know the case that causes minimum number of operations to be executed. In the linear search problem, the best case occurs when x is present at the first location. The number of operations in the best case is constant (not dependent on n). So time complexity in the best case would be (1)
Most of the times, we do worst case analysis to analyze algorithms. In the worst analysis, we guarantee an upper bound on the running time of an algorithm which is good information
example : sorting algorithmn
Algorithm
Time complexity:Best
Time complexity:Average
Time complexity:Worst
Space complexity:Worst
Quick sort
O(n log(n))
O(n log(n))
O(n2)
O(n)
Merge sort
O(n log(n))
O(n log(n))
O(n log(n))
O(n)
Heap sort
O(n log(n))
O(n log(n))
O(n log(n))
O(1)
Bubble sort
O(n)
O(n2)
O(n2)
O(1)
Insertion sort
O(n)
O(n2)
O(n2)
O(1)
Selection sort
O(n2)
O(n2)
O(n2)
O(1)
solution(a):
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
first pass:
4,5,3,1,2-----> 4 5 3 1 2 (Here, algorithm compares the first two elements,no swapp happens since 4 and 5 are in order)
4 5 3 1 2------> 4 3 5 1 2(swap since 5>3)
4 3 5 1 2------> 4 3 1 5 2(swap since 5>1)
4 3 1 5 2------>4 3 1 2 5(swap since 5>2)
second pass:
4 3 1 2 5------>3 4 1 2 5(swap since 4>3)
3 4 1 2 5------>3 1 4 2 5(swap since 4>1)
3 1 4 2 5------>3 1 2 4 5(swap since 4>2)
3 1 2 4 5------>3 1 2 4 5(Now, since these elements are already in order (4< 5), algorithm does not swap them.
Third Pass:
3 1 2 4 5 ------>1 3 2 4 5 (swap since 3>1)
1 3 2 4 5------>1 3 2 4 5 (swap since 3>2)
1 3 2 4 5 ------>1 3 2 4 5(Now, since these elements are already in order (4> 2), algorithm does not swap them
1 3 2 4 5 ------>1 3 2 4 5(Now, since these elements are already in order (4< 5), algorithm does not swap them.
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
fourth pass
1 3 2 4 5------>1 3 2 4 5(no swapping since it is in order)
1 3 2 4 5 ------>1 2 3 4 5(swapp since 3>2)
1 2 3 4 5------>1 2 3 4 5(Now, since these elements are already in order (3< 4), algorithm does not swap them.)
1 2 3 4 5----->1 2 3 4 5 (Now, since these elements are already in order (4< 5), algorithm does not swap them.)
solution (b)
Loop Invarient:
Loop invariant should describe the goal of the algorithm. It should hold true just before entering the loop and after each iteration. It should give an idea about the current progress towards the final goal. In the case of bubble sort we have an outer loop and an inner loop so we have two invariants not only one. We can think of the inner loop as the implementation of the outer loop then only think about the outer loop. After that, we find an appropriate invariant for the inner loop. Imagine the array is split into two sections around some position (i). Assume elements to the right of (i) are sorted and the ones to the left of (i) are not. The inner loop pushes the largest element from the unsorted section to its correct place in the sorted section. On the other hand, the outer loop pushes the position (i) to the left each iteration until all elements are in the correct place. As you can see, as the outer loop progresses, the sorted section grows and the unsorted section shrinks. The outer loop invariant should give us an idea about this sorting progress. Let us try to use the following invariant for the outer loop "Elements to the right of (i) are sorted". Similarly, the inner loop bubbles up the largest element in the unsorted section to the sorted section on right side of the array. The inner loop invariant should also give us an idea about what the inner loop does so let us use the invariant: "The bubbling element at position (j) in the unsorted section is the greatest element in the first (j) elements". We will verify that these invariants hold true before and after each iteration in each loop
Let us first work on the outer loop. Before entering the loop there should be no sorted section yet. This means we should initialize (i = n). Apply that to the outer invariant as follows:
The number of array elements in the range (n + 1) to (n) is zero. In other words:
This makes sense because the array is not sorted yet before entering the outer loop. In order to prove that the outer invariant holds true after each iteration, let us test the first iteration when (i = n - 1). Apply that to the invariant:
This means A[n] to the right of (n - 1) is sorted. Now take the second iteration when (i = n - 2) just to be sure:
This means the last two elements in the array are now sorted and in the right place so the invariant holds after each iteration. Now let us see what happens when the outer loop terminates. The outer loop terminates when (i = 1). Apply that to the invariant:
This basically says all elements except the first one are sorted and in the right place. This is nothing but saying the whole are array is now sorted because the first element is in its correct place. In other words the post condition or the goal of the loop has been achieved. Please pay attention that the outer loop index (i) is decremented after the inner loop (not before) otherwise the outer loop invariant will not hold true after the first iteration. The reason why it will not hold true if we do so is because the inner loop is used to push one element at a time from the unsorted section to the sorted section.
solution (C): correctness method:
Let A' denote the output of BUBBLESORT(A). To prove that BUBBLESORT iscorrect, we need to prove that it terminates and that A'[1] A'[2] ... A'[n]
where n = A.length. In order to show that BUBBLESORT actually sorts,
Loop Invariant:At the beginning of each iteration of the loop the elements in A[k..n] are a permutation of the elements that were originally in A[k..n] at the start of the first iteration of the loop such that A[k] contains the smallest element in A[k..n].
Initialization:At the beginning of the first iteration i== 1 and i<=n. Because n is defined as A.length it is trivial to see that A[k] is the minimum value in A[k..n] and that it is a permutation of the starting order of A[k..n]
Maintenance:
As per the Termination condition of the inner loop, when the next iteration occurs the values that are in A[1..i-1] will be the smallest value of the previous iterations' inner loops. Therefore A[1..i-1] will be in sorted order and smaller than the elements of A[i..n]. As the inner loop only creates permutations of A, A will still be a permutation of the initial array.
Termination:
When the loop ends i will be equal to n. Therefore, when the loop ends the first i-1 elements will be in sorted order and less than the remaining values in A[i..n]. Because A[i..n] is simply the single element array A[n] and it guaranteed to contain only elements larger than the elements in the subarray A[1..i-1] we can conclude that A[1..n] is in sorted order
solution: the best case and worst case of bubble sort
The worst case running time of bubblesort is (n^2) because it relies on a for loop within a for loop which both iterate over the array.
The best case running time of bubblesort is (n^2)
Algorithm
Time complexity:Best
Time complexity:Average
Time complexity:Worst
Space complexity:Worst
Quick sort
O(n log(n))
O(n log(n))
O(n2)
O(n)
Merge sort
O(n log(n))
O(n log(n))
O(n log(n))
O(n)
Heap sort
O(n log(n))
O(n log(n))
O(n log(n))
O(1)
Bubble sort
O(n)
O(n2)
O(n2)
O(1)
Insertion sort
O(n)
O(n2)
O(n2)
O(1)
Selection sort
O(n2)
O(n2)
O(n2)
O(1)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.