Question

Determine the order of complexity for the following algorithm: function(int n) { int l, u, m;...

Determine the order of complexity for the following algorithm:

function(int n) {
int l, u, m;
   l=0; u= n-1;
   while (l<u) {
       m= (l+u)/2;
       if (a[m] < x) l= m+1;
       else if (a[m] >x) u=m-1;
           else return “found”
   }
   return (“not found”);
}

Homework Answers

Answer #1
Each time in the while loop the size is getting decreased by 2
and in each time it is taking some constant time c.

So, Recurrence relation is
T(n) = T(n/2) + c

Solving Recurrence relation
T(n) = T(n/2) + c
     = T(n/4) + c + c
     = T(n/8) + c + c + c
     ......
     ......
     ......
     = T(n/n) + c + .... + c + c + c [log(n) +1 terms]
     = c + c + .... + c + c + c [log(n) +1 terms]
     = clog(n)
     = O(logn)


O(logn)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
What does the following function compute? Give an analysis of its complexity int fun1 (int n)...
What does the following function compute? Give an analysis of its complexity int fun1 (int n) { if (n == 0)     return 1; else      return fun1(n-1) + fun1(n-1); }
Draw a program flow graph for the function below int binsearch(int x,int v[],int n) { int...
Draw a program flow graph for the function below int binsearch(int x,int v[],int n) { int low,high,mid; low=0; high=n-1; while(low<high) { mid = ( low + high ) / 2; if( x < v[mid]) high = mid - 1; else if ( x > v[mid]) low = mid + 1; else return mid; } return -1; }
Given the following function: int bar(int n) {     if( n < 0 )         return...
Given the following function: int bar(int n) {     if( n < 0 )         return -2;     else if (n <= 1)         return 2;     else       return (3 + bar(n-1) + bar(n-2)); } What is returned by bar (4)? Show all the steps
QUESTION 1 For the following recursive function, find f(5): int f(int n) { if (n ==...
QUESTION 1 For the following recursive function, find f(5): int f(int n) { if (n == 0)    return 0; else    return n * f(n - 1); } A. 120 B. 60 C. 1 D. 0 10 points    QUESTION 2 Which of the following statements could describe the general (recursive) case of a recursive algorithm? In the following recursive function, which line(s) represent the general (recursive) case? void PrintIt(int n ) // line 1 { // line 2...
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1]...
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1] of real numbers if n = 1 return T[0] else temp ← Test (T[0..n − 2]) if temp ≥ T[n − 1] return temp else return T[n − 1] a. What does this algorithm compute? b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.
Consider the following recursive algorithm Algorithm S(n) if n==1 return 1 else return S(n-1) + n*n*n...
Consider the following recursive algorithm Algorithm S(n) if n==1 return 1 else return S(n-1) + n*n*n 1)What does this algorithm compute? 2) Set up and solve a recurrence relation for the number of times the algorithm's basic operation is executed. 3) How does this algorithm compare with the non-recusive algorithm for computing thius function in terms of time efficeincy and space effeciency?
Given the following algorithm, matching each statement to the correct sequence for complexity analysis. procedure Alg3(A):...
Given the following algorithm, matching each statement to the correct sequence for complexity analysis. procedure Alg3(A): A is a list of n integers 1 for i = 1 to n-1 do 2   x=aix=ai 3 j = i − 1 4 while (j ≥≥ 0) do 5 if x≥ajx≥aj then 6 break 7 end if 8   aj+1=ajaj+1=aj 9 j = j − 1 a end while b   aj+1=xaj+1=x c end for d return A The complexity of this algorithm is O(n2)O(n2)...
Analyze the worst-case complexity of the algorithm below when using an optimized adjacency list to store...
Analyze the worst-case complexity of the algorithm below when using an optimized adjacency list to store G. ComponentCount: Input: G = (V, E): an undirected graph with n vertices and m edges Input: n, m: the order and size of G, respectively Output: the number of connected components in G Pseudocode: comp = n uf = UnionFind(n) For v in V:     For u in N(v):         If (uf.Find(v) != uf.Find(u))             uf.Union(u, v)             comp = comp - 1...
Analyze the worst-case complexity of the algorithm below when using an optimized adjacency list to store...
Analyze the worst-case complexity of the algorithm below when using an optimized adjacency list to store G. ComponentCount: Input: G = (V, E): an undirected graph with n vertices and m edges Input: n, m: the order and size of G, respectively Output: the number of connected components in G Pseudocode: comp = n uf = UnionFind(n) For v in V:     For u in N(v):         If (uf.Find(v) != uf.Find(u))             uf.Union(u, v)             comp = comp - 1...
In this programming exercise you will create an algorithm for solving the following version of the...
In this programming exercise you will create an algorithm for solving the following version of the m Smallest Numbers problem.   Instead of just returning the m smallest values as in homework 1, you want to return a list of the positions where the m smallest values are located without changing the original array. Your algorithm should meet the following specifications: mSmallest( L[1..n], m ) Pre: L is a list of distinct integer values. n is the number of elements in...