![Part a: Use the definitions of big-o notation and little-o notation to prove that if J(r) oig (a)), it mist be true that f(r) o(g(T). Do nal rse the limit theorem to prove this: you can only use the definitions of big-O and little-o notation. Part b: Destribe the rumming time of the algorithm below as a recurrence relation, and use the Master Theorem to analyze its running time. function ExcLUDEDMIDDLESEARCI (array B, int r) 2: if length (B) 1: return Blol else B1 B10 length (B)/4] B2 BB length (B)/4 length (B)] return ExcludedMiddlesearch(B1) or ExcludedMiddle- Search(B2) 8: end function](https://d2vlcm61l7u1fs.cloudfront.net/media%2Fcf4%2Fcf4ec125-0f12-43da-98b9-1f2042cd5952%2FphpPQErIT.png)
Use the definitions of bog-O notation and little-o notation to prove that if f (x0 = o(g(x)), the must be turn that f(x) = O(g(x)). Do not use the limit theorem to prove this: you can only use the definitions of big -O and little-o notation. Describe the running time of the algorithm below as a recurrence relation, and use the Master Theorem to analyze its running time. function Excluded Middle Search (array B, int x) if length (B) = = 1; return B[0] = = x else B1 leftarrow B[0;length (B)/4] B2 leftarrow B [3 length (B)/4;length (B)] return Excluded Middle Search (B1) or Excluded Middle-Search (B2) end function.
