Find the best O(g(n)) notation describe the complexity of the algorithms listed
ID: 3798338 • Letter: F
Question
Find the best O(g(n)) notation describe the complexity of the algorithms listed in parts (a) through (d) below. Choose the g(n) from the following list and justify your claims. I, log_2 n, n, n, log_2 n, n^2, n^3, n^4, 2^n, n! An algorithm that lists all ways to put the numbers 1, 2, 3 n in a row. An iterative algorithm to compute n!, counting the number of multiplications) An algorithm that finds the average of n numbers by adding them and dividing by n^2 An algorithm that prints all subsets of size four of the set 1, 2, 3, ..., n.Explanation / Answer
a) Algorithm:
All_ways(int a[],int left, int right)
{
int i
if(left==right){ print (a) }
else
{
for(i=0;i<right;i++)
{ swap((a+left), (a+i));
All_ways(a, left+1, right);
swap((a+left),(a+i));
}
}
}
complexity of this program is O(n!)
explanation:
for a list of size n, the all possible permutations are n!, so the alogithm has to run upto n! times
hence the complexity is O(n!)
b)algorithm:
factorial(n)
{
int i=1,k=1;
while(i<=n)
{
k=k*i;
i=i+1;
}
return k
}
Complexity : O(n)
explanation: n! = 1*2*3*...*n..
so, we have to multiply all numbers from 1 to n iteratively, using any loop, we have to run it from 1 to n
hence the complexity is O(n)
c)algorithm
average(int a [])
{
int i,k;
while(i<n)//n - size of array a
{
k=k+a[i]//calculating sum
i=i+1
}
return k/n^2
}
complexity : O(n)
explantion : for finding average... first we need to add all n elements of array, for this we have to use a loop which runs from 1 to n.. hence the complexity is O(n)
d)
1)first create a boolean array with the size of given array
2)now for every integer we have whether to select it or not..if we select a integer then we put a TRUE in boolean array at corresponding position, otherwise FALSE
3)we start with length=0, and do recursive calls ,for both the options mentioned above
4)if we selected an integer to 1 then make length =length+1 other wise don't change length
5)Another important factor is from which index you will start making the subset of size k. Initialize s=0 and with every recursive call, make s + 1 ( for both the scenarios mentioned in the steps above).
6)print elements when current length =k..
the complexity: O(2^k)
explantion:to generate k length substring, first find 1 length,then 2 length, then 3 length...........then finally k lenght... this is similar to finding power set to list length k, hence complexity is O(2^k)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.