Name: NORHAMDI N.
SAMSON
Yr.& Course: 2nd yr.BS Information Technology
Subject:5450 ITC - DATA STRUCTURES AND ALGORITHMS
ASSIGNMENT:
1.What is Asymptotic Analysis?
Asymptotic analysis is the process of calculating the running time of an algorithm in mathematical units
to find the program's limitations, or “run-time performance.” The goal is to determine the best case,
worst case and average case time required to execute a given task.
2.What is the worst average and best case of Algorithm with Examples?
In computer science, best, worst, and average cases of a given algorithm express what the resource
usage is at least, at most and on average, respectively. Usually the resource being considered is running
time, i.e. time complexity, but could also be memory or some other resource. Best case is the function
which performs the minimum number of steps on input data of n elements. Worst case is the function
which performs the maximum number of steps on input data of size n. Average case is the function
which performs an average number of steps on input data of n elements.
Example:
Insertion sort applied to a list of n elements, assumed to be all different and initially in random
order. On average, half the elements in a list A1 ... Aj are less than element Aj+1, and half are
greater. Therefore, the algorithm compares the (j + 1)th element to be inserted on the average
with half the already sorted sub-list, so tj = j/2. Working out the resulting average-case running
time yields a quadratic function of the input size, just like the worst-case running time.
Quicksort applied to a list of n elements, again assumed to be all different and initially in
random order. This popular sorting algorithm has an average-case performance of O(n log(n)),
which contributes to making it a very fast algorithm in practice. But given a worst-case input, its
performance degrades to O(n2). Also, when implemented with the "shortest first" policy, the
worst-case space complexity is instead bounded by O(log(n)).
Heapsort has O(n) time when all elements are the same. Heapify takes O(n) time and then
removing elements from the heap is O(1) time for each of the n elements. The run time grows to
O(nlog(n)) if all elements must be distinct.
Bogosort has O(n) time when the elements are sorted on the first iteration. In each iteration all
elements are checked if in order. There are n! possible permutations; with a balanced random
number generator, almost each permutation of the array is yielded in n! iterations. Computers
have limited memory, so the generated numbers cycle; it might not be possible to reach each
permutation. In the worst case this leads to O(∞) time, an infinite loop.
3.What is Asymptotic notations?
Asymptotic notations are the mathematical notations used to describe the running time of an algorithm
when the input tends towards a particular value or a limiting value. For example: In bubble sort, when
the input array is already sorted, the time taken by the algorithm is linear i.e. the best case.
4.Comparison between complexity of sorting techniques.
In comparison based sorting, elements of an array are compared with each other to find the sorted
array. Best case time complexity: n when array is already sorted. Worst case: when the array is reverse
sorted. Best, average and worst case time complexity: n^2 which is independent of distribution of data.
5.Growth weight of complexities.
