In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

Consider the following algorithm for searching for a given number x in an unsorted array A[1..n] having n distinct values:
1. Choose an i uniformly at random fro 1..n;
2. If A[i]=x then stop else Goto 1;
Assuming that x is present A, what is the expected number of comparisons made by the algorithm before it terminates?

The running time of the following algorithm Procedure A(n)
If n<=2 return (1) else return (A([$$\sqrt n $$])); is best described by

The solution to the recurrence equation
T(2^k) = 3 T(2^k-1) + 1, T (1) = 1, is: