DATA STRUCTURES
ANALYSIS OF ALGORITHMS
Definition:-
The method of solving a problem is known as an algorithm.It is a sequence of instructions that act on some input data to produce some output in a finite number of steps.
Properties:-
a) Input:An algorithm must receive some input data supplied externally.
b)Output:An algorithm must produce atleast one output as the result.
c)Finiteness:The algorithm must terminate after a finite number of steps.
d)Definiteness:The steps to be performed in the algorithm must be clear and unambiguous.
e)Effectiveness:One must be able to perform the steps in the algorithm without applying any intelligence. All algorithms basically fall under two broad categories-Iterative and Recursive algorithms. Iterative Algorithms typically use loops and conditional statements. Recursive Algorithms use a divide and Conquer strategy. As per this,the recursive algorithm breaks down a large problem into small pieces and then applies the algorithm to each of these smal pieces. Determining which algorithm is efficient than the other involves analysis of algorithms. While analyzing,time required to execute it determined .’time’ represents the number of operations that are carried out while executing the algorithm. While analyzing iterative algorithms we need to determine how many times the loop is executed. To analyze a recursive algorithm one needs to determine amount of work done for three things:
i.breaking down the large problem to smaller pieces. ii.Getting solution for each piece and combining the individual solutions to get the solution to the whole problem. iii.Combining this information and the number of the smaller pieces and their sizes,we then need to create a recurrence relation for the algorithm.
Analysis:-
The analysis of an algorithm provides information that gives us a general idea of how long an algorithm willtake for solving a problem.For comparing the performance of two algorithms we have to esimate the time taken to solve a problem using each algorithm for a set of N input values. Analysis of algorithms give us the scientific reason to determine which algorithm should be chosen to solve the problem. The purpose of determining the number of comparisions is to then use them to figure out which of the algorithms under consideration can solve the problem more efficiently.
What Analysis Doesn’t Do:-
The analysis of algorithms does not give a formula that helps us determine how amny seconds or computer cycles a particular algorithm will take to solve a problem. The analysis of algorithm should be done regardless of the computer on which the program that implements the algorithm is going to get executed.
Things to Count and Consider:- i.The significant operation or operations in the algorithm must be identified first. ii.Operations integral to the algorithm and which merely contribute to the overheads should be determined next. Comparision or arithmetic are two classes of operations that typically chosen for the significant operation.
Cases To Consider During Analysis:- Multiple input sets must be considered while analyzing an algorithm. a)Best Case Input:- This represents the input set that allows an algorithm to perform most quickly with this input the algorithm takes shortest time to execute, as it causes the algorithms to do the least amount of work. No matter how large is the input,searching in a best case will result in a constant time of 1. Since the best case for an algorithm would usually be very small and frequently constant value,a best case analysis is often not done. b)Worst Case Input: This represents the input set that allows an algorithm to perform more slowly.Worst case is an important analysis because it gives us an idea of the most time an algorithm will ever take. Worst case analysis requires that we identify the input values that cause an algorithm to de the most work. c)Average Case Input: This represents the input ser that allows an algorithm to deliver an average performance. Doing average case analysis is a four step process.
These steps are as follows: i.Determine the number of different groups into which all possible input sets can be divided. ii.Determine the probability that the input will come from each of these groups. iii.Determine how long the algorithm will run for each of these groups. All of the input in each group should take the same amount of time,amd if they do not,the group must be split into separate groups.
Calculate average case time using the formula: m A(n)=∑pi*ti where i=1 n=size of input m=number of groups pi=probability that the input will be from group i

ti= time that the algorithm takes for input from group i.
Rates Of Growth:- While doing analysis of algorithm we must consider what happens when the size of the input is large, because small input sets can hide rather dramatic differences.
Algorithms can be groped into three categories based on the order of the function or related algorithm. a)Algorithm that grow atleast as fast as same function. b)Algorithms that grow at the same rate. c)Algorithms that grow no faster. The categories mentioned above are commenly known as Big Omega Ω (f),Big oh O(f) and Big Theta Ө(f) respectively. Of these, the Big Omega category of functions is not of much interest o us since for all values of ‘n’ greater than same threshold value no all the functions in Ω (f) have values that are at least as large as f(i.e) all functions in this category grow as fast as f or even faster. Big Oh O(f) category represents the class of functions that grow no faster than f. This means that for al values of n greater than same threshould number all the functions in O(f) have values that are no greater than f.
Analysis of sequential search Algorithms:
Sequential Search looks at elements,one at a time,from the first in the list until a match is found .It returns the index of where the value being searched is found. If the value is not found the algorithm returns an index value that is outside the range of the list of elements.
Assuming that the elements of the list are located in positions 0 to N-1 in the list, we can return a value-1 if the element being searched is not in the list.
Sequentialsearch (list,value,N)
List-the elements to be searched value-the elementto be searched for n- the number of elements in the list for i=1 to N do
If(value=list[i])
returm i end if end for return 0
Worst Case Analysis:
These are two worst case for the sequential search algorithm:
-The value being searched matches the last element in the list
-The value being searched is not present in the list.
Average Case Analysis:
There are two average case analyzes that can be done for a search algorithm. The first assumes that the search is always successful and the other assumes that the value being searched will sometimes not be found.
Performance Analysis:
Criteria upon which can judge an algorithm includes.
1.Does it do what we want it to do
2.Does it work correctly according to the original specifications of the task?
3.Is there documentation that describes how to use it and how it works?
4.Are procedures created in such a way that they perform logical sub functions?
5.Is the code readable?
These are other criteria for judging algorithms that have a more direct relationship to performance. These have to do with their computing times and storage requirements.
Space Complexity:
The space complexity of an algorithm is the amount of memory it needs to run to completion.
1)Example: Algorithm abc(a,b,c)
{
return a+b+b*c+(a+b-c)/(a+b)+4.0;
}
Algorithm abc computes a+b+b*c+(a+b-c)/(a+b)+4.0;
2)Example: Algorithm sum(a,n)
[ s:=0.0; for i:=1 to n do s:=s+a[i]; return s;
}
n
Algorithm sum computes ∑a[i] iteratively where the a[i] s are real numbers. I=1

3)Example: Algorithm Rsum(a,n)
{
if(n=100n for n>=1
3)Definition:-[Theta]
The function f(n)= Ó¨ (g(n)) iff there exists positive constants c1, c2 and n0 such that c1g(n)=3n for all n>=2 and 3n+2=2,so c1=3,c2=4 and n0 =2.
The theta notation is more precise than both big oh and omega notations.
4)Definition:-[little oh] The function f(n)= o(g(n)) iff lim f(n)/g(n) =0 n->∞
Ex:3n+2=o(n²) since lim 3n+2/n2 =0 n->∞

5)Definition:-[little omega] The function f(n)= w(g(n)) iff lim g(n)/f(n) =0 n->∞

The BIG OH NOTATION:
If f(n) and g(n) are functions defined for positive integers,then to write f(n) is O(g(n)) which means that there exists a constant C such that |f(n)|f(n)-O(g(n)) if there exists two constants C and no such that |f(n)|= no .
Utility:
f(n) will normally represent the computing time of some algorithm. When we say that the computing time of an algorithm is O(g(n)) we mean that its execution takes no more than a constant times g(n).n is a parameter which characterizes the input and/or output.
i)Big O is transitive:-
It is easy to show that if f(n) is O(g(n)) is O(h(n)),f(n) s O(h(n)).
e.g:n³+100n is O(n²),n² is and O( n³ ) consequently n² +100n is O( n³ ). This is called transitive property. ii)Big O is multiplicative:
A constant computing time is referred to as O(1),O(1) is better than O(n),which in tern is better than O(n²).O(n³)is worse and O(2^n) is awful.
One other frequently seen computing time is O(log n base 2)which is better than O(n).
Its complexity increases in multiple as n increases,hence it is multiplicative. Total number of key comparisons by Quick Sort algorithm for an unordered array is O(nlog n) and for ordered array is O(n²).
For an unsorted array if we are lucky then each time a record is correctly positioned the subfile to its left will be of the same size as that to its right. This would leave us with the sorting of two subfiles each of size roughly n/2. The time required to position a record in the file of size n is O(n). If T(n) is the time taken to sort a file of n records then when the file splits roughly into two equal parts each time a record is positioned correctly we have
T(n)infinitef(n)/g(n)=0
7)The function f(n)=w(g(n)) iff

a)lim n->infiniteg(n)/f(n)=1 b)lim n->infiniteg(n)/f(n)=0 c)lim n->0g(n)/f(n)=1 d)lim n->0g(n)/f(n)=0 8)The running time of an algorithm is given by T(n)=T(n-1)+T(n-2)-T(n-3),if n›3 n,otherwise. The order is a)n b)log n c)nn d)n2 9)What should be the relation between T(1),T(2) and T(3),so that above question gives an algorithm[a] a)T(1)=T(2)=T(3) b)T(1)+T(3)=2T(2) c)T(1)-T(3)=T(2) d)T(1)+T(2)=T(3) 10) Time complexity of an algorithm T(n),where n is the input size is given by T(n)=T(n-1),where n is the input size is given by T9n)=T(n-1)+1/n,if n› =1,otherwise The order of this algorithm is[a] a)log n b)n c)n2 d)nn 11)Which of the following sorting algorithm has the worst time complexity of nlog n?[a] a)heap sort b)Quichk sort c)Insert sort d) Selection sort 12) THe concept of order (Big O) is important because [d] a)it can be used to decide the best algorithm that solves a given problem b)it determines the maximum size of a problem that can be solved in a given amount of time. c)it is the lower bound of the growth rate of algorithm d)both (a) and (b)above 13)The running time T(n),where n is the input size of a recursive algorithm is given[b] T(n)=c+T(n-1),if n› =d,if n‹=1 The order of the algorithm is a)n2 b)n c)n3 d)nn Ex: Recursively applying the relation,we finally get T(n+1)=C(n-1)+t(1)=C(n-1)+d hence order is n. 14) Consider the following two functions f(n)=n3, if 0‹=n‹10,000 =n2,otherwise g(n)=n,if 0‹=n‹100 =n2+5n,otherwise which of the following are true.[c,d] a)f(n) is O(g(n)) b)g(n)is O(n3) c)O(f(n))is same as O(g(n)) d)g(n) is O(n2) 15)An algorithm is made up of 2 modules M1 and M2.If order of M1 is f(n) and M then the order of the algorithm is[a] a)max(f(n),g(n)) b)min(f(n),g(n)) c)f(n)+g(n) d)f(n)*g(n) By definition of order ,there exists constants c1,c2,n1n2such that T(n)‹=c1*f(n),for all n‹=n1 T(n)‹=c2*g(n),for all n‹=n2 Let N=max(n1,n2) and c=max(c1,c2) so, T(n)‹=c*f(n),for all n‹=N T(n)‹=c*g(n),for all n‹=N Adding T(n)‹=c/2*(f(n)+g(n)) withhout loss of generality,let max(f(n),g(n))=f(n) T(n)‹=c/2(f(n)+f(n))‹=c*f(n) so,order is f(n),which is max(f(n),g(n)),by our assumption. 16)Big O is[c] a)multiplicative b)transitive c)both d)none of these

Questions:
1.Determine the frequency counts for all statements in the following two algorithm segments:
1.for i:=1 to n do 1.i:=1;
2.for j:=1 to i do 2.while(in); i:=1; while(i