I need help with the following Algorithms assignment:

1. Show that for any real constants a and b, where > 0, ( + ) = ( )

2. Find a theta notation for the number of times the statement = + 1 is executed.

i = 2

while ( i < n) {

i = i * i x = x + 1

}

3. What does the following algorithm do (What is the output)? Analyze its worst-case running time, and express it using Big-Oh notation.

Algorithm Foo (A, n):

Input: An array A storing 1 integers.

Output: ??

= [0]

for = 1 to 1 do

if < [] then

= []

return K

4. Determine whether each statement is true or false. Justify your answer

a) = (2 )

b) If () = (()), then () = (())

c) 2 +1 = (2 )

5. Show that 2 1 is ()

6. Show that 2 2 + 3 + 1 = ( 2 )

7. Show that 10 2 5 51 = ( 3 )

8. Show that 18 3 4 2 + 2 40 = ( 2 )