Log n!, Summation and Theta Relation

Prove that log n! and sum from i=2 to n log i have a theta relation to n log n.

Time Complexity of an Algorithm in Theta Notation : Calculating Time from the Number of Loops

How much time does the following algorithm require as a funciton of n? Express your answer in theta notation in the simplest form. Consider each individual instruction (including loop control) as elementary. l = 0 for i = 1 to n for j = 1 to n^2 for k = 1 to n^3 l = l + 1

Time complexity of an algorithm in theta notation

How much time does the following algorithm require as a function of n? Express your answer in "theta notation" in the simplest possible form. Show all work! l = 0 for i = 1 to n for j = 1 to i for k = j to n l = l +1

Solving recurrence exactly

Solve the following recurrence exactly for n of the form 2^2^k. T(2) = 1 T(n) = 2T(n^(1/2)) + log n Express your answer as simply as possible using theta notation. note added ** theta notation is based on big O notation Show all work!

Proof

I received the following proof, can someone show all steps of how the solution was formed? Proof: Let n=2^2^k, then we have T(n)=T(2^2^k)=2T(n^(1/2))+log n ***How do you get n^(1/2) equals 2^2^(k-1) =2T(2^2^(k-1))+2^k ***How do you get 2T(2^2^(k-1)) equals 2(2T(2^2^(k-2))+2^(k-1)) =2(2T(2^2^(k-2))+2^(k-1))+ ...continues

Algorithm

Let T[1..n] be a sorted array of distinct integers, some of which may be negative. Give an algorithm that can find an index i such that 1 <= i <= n and T[i] = i, provided such an index exists. Your algorithm should take a time in Big "O" (log n) in worst case.

Solving Recurrence Relations/Difference Equations

See attached file for full problem description.

Prove that any binary search algorithm on a sorted array of size n that uses only key comparisons must require at least omega (log n) comparisons in the worst case.

Prove that any binary search algorithm on a sorted array of size n that uses only key comparisons must require at least omega (log n) comparisons in the worst case.

Proof : Tree Contains a Cycle

Prove that a graph with n nodes and more than n-1 edges must contain at least one cycle.

Dynamic Programming : Write an Algorithm to Minimize Cost

There are n trading posts along a river. At any of the posts you can rent a canoe to be returned at any other post downstream. (It is next to impossible to paddle against the current.) For each possible departure point i and each possible arrival point j the cost of a rental from i to j is known. However, it can happen that ...continues