Question

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”);

}

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)

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 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 -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 == 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] 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
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): 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 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 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 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...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 3 minutes ago

asked 13 minutes ago

asked 16 minutes ago

asked 17 minutes ago

asked 20 minutes ago

asked 20 minutes ago

asked 26 minutes ago

asked 40 minutes ago

asked 50 minutes ago

asked 50 minutes ago

asked 53 minutes ago

asked 1 hour ago