Reccurence Relation

Points to learn: If P(n)denotes the running time of the insertion sort on input – size n, then we can say that P(n) = Ω(n) as insertion sort takes linear time in best case. Remember in practice we use O and Ω notations to tight upper and lower bounds respectively otherwise for any function P(n)both the following statements are correct. P(n) = Ω(0) P(n) = O(∞) Which means any algorithm will take at least zero time and at most infinity time to execute.

Definition : A recurrence is an equation or simply an inequality that describes a function in the terms of its values on smaller inputs. ☛The running time of the recursive algorithm can be obtained by a recurrence. To solve a recurrence relation means to obtain a function defined on the natural numbers that satisfies the recurrence. Example : Fibonacci series is f(n)=f(n−1)+f(n−2)..... For solving the recurrence we will discuss following methods : 1. Substitution Method. 2. Master Theorem. 3. Recursion Tree Method. 1. Substitution Method : The substitution method is a condensed way of proving an asymptotic bound on a recurrence by induction. It is able to prove upper bounds for almost all recurrences. It is used in calculating the time complexity of recurrence relations. ✍The substitution method for solving recurrences we have : ☛ Guess the form of the solution. ☛ Use mathematical induction to find the constants and show that the solution works.

Small-o notation

In small-o notation we get following informations: 1.Big –O notation is like ≤f(n) ≤ g(n) when f(n) = O(g(n)) 2. small – o notation is like

<{f(n) g(n) when f(n) = o(g(n)) 3.The asymptotic upper bound provided by O – notation may or may not be asymptotically tight. Small – o is used to denote an upper bound that is NOT asymptotically tight. 4.o(g(n)) = (f(n): for any positive constant > 0, n0 > 0, ↪ 0 ≤ f(n) < cg(n) ∀ n>n0 ) Example: 2n = {f(n)} but 2n 2 ≠ o(n 2)

Asymptotic Notations

(1) Big – oh (O) /(Big-O) After analysing an algorithm if one says T(n) = O(n 2) He means that algorithm will be completed with in cn 2 time for a sufficiently large n. Hence big – O given upper bound but this upper bound may or may not be the tightest. ⟱ iff there are positive constant c & n0 then O(g(n)) = 0 ≤ f(n) ≤c.g(n) ≤f(n) ∀ n ≥ n upper bound ↪ if f(n)=O(g(n)), we say that g(n) is an upper bond of f(n). Hence If T = O(n 2) then T = O(n 3) T = O(n 4) infact T = O(n 2+r +) [but it does NOT mean O(n 2) = O(n 3) = O(n 4) …] But first statement is more clearing the fact. keep in mind n 2 = O(n 3) ↪ one sided equality O(g(n)) = 0 ≤ f(n) ≤c.g(n) ≤f(n) ∀ n ≥ n0