5.4 Learning Objective: To demonstrate that the student understands the definition of Big O. To demonstrate that the

student understands that if a function f(n) is O(loga n) then that same function is also O(logb n), where a and b are

constants. That is, different bases for the logarithm function do not change the time complexity.

Instructions: This exercise is not graded, so you do not need to include your solution in your word processing document.

Problem: An important concept to know regarding Big O notation is that for logarithmic complexity, the base is irrelevant.

In other words, if f(n) is a function that counts the number of times the key operation is performed as a

function of n and f(n) is O(loga n) then it it also true that f(n) is O(logb n). For example, binary searchwhich is

usually stated as being O(lg n)is also O(ln n), O(log10 n), and O(log3.14159265 n). Using the formal definition of Big O,

prove mathematically that if f(n) is O(loga n) then f(n) is also O(logb n).

Hint: First, show that loga n = (loga b)(logb n). Note that (loga b) is a constant and that in the expression C g(n), C

is a constant. Next, since we are trying to show that f(n) = loga n is logb n, note that you already showed that loga n

= (loga b)(logb n).

5.5 Learning Objective: To demonstrate that the student understands the definition of Big O. To demonstrate that the

student understands how to derive the function f(n) which computes how many times the key operation of an algorithm

is performed as a function of the size of the problem.

Instructions: This exercise is graded, so include your solution in your word processing document.

Problem: Continuing with the previous exercise, derive a function f(n) which equates to the number of times the key

operation is performed as a function of n, where n is the size of pList. State the worst case time complexity of split()

in Big O notation. You do not need to formally prove it but explain your answer.

5.5 is the one I need