How to measure the time complexity of an algorithm?
A. For each of the three fragments of code, what is its worst-case time complexity, in the form "O(…)". (Use the given solution to the first problem as a model)
//----------------- This is a sample problem – solved ------
Given an array a of size N, what is the complexity?
int i=n, x=0;
while (i>0) {
i--;
x = x + a[i];
}
What is the most frequent operation performed? ___addition____________________
Expression showing the number of times it is performed____ N _______
Time Complexity in Big-O Notation____ O(N) __________________________
//1.--------------------------------------------------------------
Given three 2-dimensional arrays A, B, C of size N x N, what is the complexity?
for (int i=0; i<N; i++) {
for (int k=0; k<N; k++) {
int x=0;
for (int j=0; j<N; j++) {
x = x + A[i][j] * B[j][k];
}
C[i][k] = x;
}
}
What is a (name one) most frequent operation performed? ___________
Expression showing the number of times it is performed ______
Time Complexity in Big-O Notation___ O(_____) ___________________________
//2.--------------------------------------------------------------
Given an array of size N, what is the complexity?
int m = A[0];
for (int i=1; i<N; i++)
{ if (A[i] > m) m = A[i]; }
int k = 0;
for (int i=0; i<N; i++)
{ if (A[i] == m) k++; }
What is a (name one) most frequent operation performed?______________________
Expression showing the number of times it is performed ___________
Time Complexity in Big-O Notation O( ) _____________________________________________________
//3.--------------------------------------------------------------
int mult(int N, int M)
{
int s = 0;
while (N > 0)
{
s = s + M;
N = N-1;
}
return s;
}
What is a (name one) most frequent operation performed?______________________
Expression showing the number of times it is performed___________
Time Complexity in Big-O Notation O( ) _______________________________________________________
4. The following method computes the value of x raised to the power of n, where n is a positive integer. (For example, power(3, 4) would return the value of 34, i.e. 81. What is the time complexity of this method (as a function of n?)
public int power(int m, int n) //m raised to the power n
{
int res = 1; int p = m;
while (n != 0)
{
if (n%2 == 1)
res = res * p;
p = p*p;
n = n/2;
}
return res;
}
What is a (name one) most frequent operation performed? ______________________
Expression showing the number of times it is performed___________
Time Complexity in Big-O Notation O( ) ____________________________________________________
B. For each of the following problems, think about an algorithm to solve it. Write a segment of java code showing how you would solve it (i.e. code your algorithm in Java) analyze the algorithm and indicate its time complexity. Assume that a and b are integer arrays of size N.
Here is a sample solved problem: An algorithm to decide if a given number is a prime number:
public boolean isPrime(int n)
{
if (n == 2)
return true; //Done, we already know n is prime
int div = 3; //start the possible divisors at 3
while (div < Math.sqrt(n))
{
if ( n % div == 0) //we found a divisor
return false; //so n is not prime
div = div + 2; //if not, try the next number
}
return true; //No divisor was found. So, num is a prime
}
Analysis of the algorithm (example):
Typical Operation: % or +
Number of times performed: Goes up to sqrt(n), increments by 2, therefore in the worst case this is done n1/2 / 2 times
Time complexity = n1/2
a. Print the value at the middle of the array (You can assume that the length of the array is an odd number). (Example: if a = {5, 3, 6, 2, 1} it should print 6.)
Time Complexity of above problem in Big-O Notation O( )
b. Print the smallest element of the array a (assuming that a is NOT sorted)
Time Complexity of above problem in Big-O Notation O( )
c. Print the smallest element of the array a (assuming a is sorted in ascending order)
Time Complexity of above problem in Big-O Notation O( )
d. A "pair" is two consecutive locations in the array having the same value. (Note: {2, 3, 3, 4, 2} has a pair 3, 3. But, {4, 5, 2, 9, 2} doesn't have a pair). Find if the array a has a pair in it.
Time Complexity of above problem in Big-O Notation O( )
e. Find if any two values in the array are the same (i.e. a has a repeated element). For example {2,3,3,4,2} has two repeated elements but {4,5,2,9,6} doesn't have repeated elements.
Time Complexity of above problem in Big-O Notation O( )
A)
1)
2)
3)
4)
B)
a) A simple way to solve this is storing the half of size of array in a variable and printing the element of array at that particular index.
Ex : A={5,3,6,2,1} . Size of array(N)=5; k=N/2=2.
Now, A[2]=6 i.e middle element of array.
We get correct answer always because size of array is odd.
int k=N/2,x; //where N is the size of array
x=A[k];
return x;
Analysis:
Since there is no loop and the no. of operations do not depend on value of N time complexity will be O(1)
Time complexity : O(1)
b)
int x=INT_MAX; //initializing x as maximum int value
for(int i=0;i<N;i++)
{
if(x<A[i]) { x=A[i]; }
}
return x;
Analysis :
There is just one simple loop that runs N times.
Time complexity : O(N)
c)
Since,the array is sorted in ascending order the 1st element will be the smallest.
int k=A[0];
return k;
Analysis:
Since there is no loop and the no. of operations do not depend on value of N time complexity will be O(1)
Time complexity : O(1)
d)
int flag=0;
for(int i=0;i<N-1;i++)
{
if(A[i]==A[i+1]) flag=1;
}
if(flag==1)
System.out.println("Pair exists" );
else
System.out.println("Pair doesn't exist");
Analysis :
There is just one simple loop that runs N times.
Time complexity : O(N)
e)
int flag=0;
for(int i=0;i<N;i++)
{
for(int j=i+1;j<N;j++)
{
if(A[i]==A[j]) flag=1;
}
}
if(flag==1)
System.out.println("repeated elements exist" );
else
System.out.println("repeated elements do not exist");
Analysis :
There are 2 nested loops, each runs N times.So 2 loops N*N times.
Time complexity : O(N^2)
Get Answers For Free
Most questions answered within 1 hours.