please answer questions 1,2,3,4,6 Topic outline 1. Algorithm Complexity Analysis
ID: 3837605 • Letter: P
Question
please answer questions 1,2,3,4,6
Topic outline 1. Algorithm Complexity Analysis. a. Be able to explain what the dominate term is b. Expressing algorithm complexity in "Big-Oh" notation 2. Know the complexity of the add, remove," and "lookup' operations of every data structure we discussed in class. 3. Recursive Algorithm Analysis a. Be able to explain what recurrences and initial conditions are b. Be able to identify the basic operation of a recursive function c. Be able to set up a recurrence and initial condition for a recursive function 4. Recursion a. Know how to identify the base case b. Know how to follow recursive calls. Example: public static int quest (int x, int y) if (x y) return x; else return y quest (x-1 y 1) What will be retumed as a result of the call quest(4,3). AnswerExplanation / Answer
Answers:
1)a) In algorithm time complexity analysis comparisons are normally made for large values of the input size.this means that the dominant term in the function is important term.
For example take bubble sort and see that time taken can be estimated as :a*n^2 + b*n + c here where n is the number of elements to be sorted and a,b,c are constant then for large n the dominant term is clearly n^2 and we can ,in effect,ignore the other two terms.
b)computational complexity expressed in big-o notation:
The time complexity of an algorithm is commonly expressed using big O notation, which excludes coefficients and lower order terms. When expressed this way, the time complexity is said to be described asymptotically, i.e., as the input size goes to infinity.
->Now the most common metric for calculating time complexity is Big O notation. This removes all constant factors so that the running time can be estimated in relation to N, as N approaches infinity.
Above we have a single statement. Its Time Complexity will be Constant. The running time of the statement will not change in relation to N.
The time complexity for the above algorithm will be Linear. The running time of the loop is directly proportional to N. When N doubles, so does the running time
This time, the time complexity for the above code will be Quadratic. The running time of the two loops is proportional to the square of N. When N doubles, the running time increases by N * N.
Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm differ by at most a constant factor.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.