Algorithms Questions

• We proved that the running time of mergesort is T(n)=n*lg(n) under the following condition
  
  
  
  T(n) = 0 if n = 1
  
  
  
  T(n) = 2T(n/2) + n if n > 1
• 1) Prove by telescoping that T(n) = cn*lg(n) + cn under the following condition:
  T(n) = c if n = 1
  
  
  
  T(n) = 2T(n/2) + cn if n > 1
• 2) Explain why T(1)'s values above 0 versus c when n = 1 will not matter for comparing algorithms. Give an example of a hypothetical situation when you implement a search engine in terms of the search volume and execution time required to complete the search.
• 3) Explain why the following two versions of running time will not make a difference in terms of algorithm analysis using the asymptotic notation. Also, explain in terms of growth the condition where cn will not matter in relation to cn*lg(n).
  cn*lg(n) + cn
  
  
  
  n*lg(n)
  Click Here To Get More on This Topic......