Question

How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...

How to measure the time complexity of an algorithm?

  1. Identify an important operation in the algorithm that is executed most frequently.
  2. Express the number of times it is executed as a function of N.
  3. Convert this expression into the Big-O notation.

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(          )

Homework Answers

Answer #1

A)

1)

  • Addition of x with the product of A[i][j] and B[j][k].
  • N
  • O(N^3)

2)

  • Checking the condition whether A[i] > m
  • N
  • O(N)

​​​​​​​3)

  • Addition
  • N
  • O(N)

​​​​​​​4)

  • Division of n by 2.
  • N
  • O(logN)

​​​​​​​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)

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
Use Big-O Notation to characterize the computational cost of algorithm A1 and A2. The complexity of...
Use Big-O Notation to characterize the computational cost of algorithm A1 and A2. The complexity of A1 is 10000 * n, with n being the number elements processed in A1. The complexity of A2 is 100 * n, with n elements in A2. State in Big-O notation the cost of f1, with f1(x) = log2(2x) – 14x + 3 sqrt(x) + 12x^2 - 150 this is also a theoretical question just answer no code.
Given the recursive bubble sort algorithm, analyze its time complexity in terms of Big O. bubbleSort(A[],...
Given the recursive bubble sort algorithm, analyze its time complexity in terms of Big O. bubbleSort(A[], n) { // Base case if (n == 1) return;    // One pass of bubble sort. After // this pass, the largest element // is moved (or bubbled) to end. for (i=0; i<n-1; i++) if (A[i] > A[i+1]) swap(A[i], A[i+1]);    // Largest element is fixed, // recur for remaining array bubbleSort(A, n-1); }
Restricted structures such as stack and queue are fast, but they do not support access in...
Restricted structures such as stack and queue are fast, but they do not support access in the key field mode. Group of answer choices True False Big O analysis evaluates an algorithm based on its _________ performance. Group of answer choices A. average-case B. best-case C. worst-case Which of the following algorithms is the fastest in speed? Group of answer choices A. Polynomial time algorithm B. Linear time algorithm C. Exponential time algorithm The following code gives an implementation of...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A. What is the best-case running time of Algorithm X? What is the worst-case running time of Algorithm X? 2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm...
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”); }
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)...
a) Suppose that a particular algorithm has time complexity T(n) = 3 x 2^n, and that...
a) Suppose that a particular algorithm has time complexity T(n) = 3 x 2^n, and that executing an implementation of it on a particular machine takes t seconds for n inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in t seconds? b) Suppose that another algorithm has time complexity T(n) = n^2, and that executing an implementation of it on a particular...
Analyze the worst case running time of the following code in “big-Oh” notation in terms of...
Analyze the worst case running time of the following code in “big-Oh” notation in terms of the variable n. a. void fdisp1(int n) { for(int i=0; i < n; i++) { for(int j=0; j < n; j++) { for(int k=0; k < n; k++) { for(int m=0; m < n; m++) { System.out.println("Hi I am Here"); } } } } } b. voidprintAllPossibleOrderedPairs(intarr[], int size) { for (int i = 0; i < size; i++) { for (int j =...
What is the time complexity of the following code? (in big-O notaion) sum = 0 count...
What is the time complexity of the following code? (in big-O notaion) sum = 0 count = 0 var1 = 0 for: i=1 to n{ sum = sum+i for j=1 to [(3i+2i)(5n)(2i)]{ var1 = sum+count} } for m = i to j*j{ sum = sum*sum var2 = sum - (count+3)}
Find the worst-case complexity of the algorithm below. Show your work. UFSizeCalc Input:  uf: Union-Find array of...
Find the worst-case complexity of the algorithm below. Show your work. UFSizeCalc Input:  uf: Union-Find array of size n Input: n: size of uf Output: size array for uf; that is, an array s such that s[r] equals the number of elements in the Union-Find tree rooted at r, for every root r (s may have any value for indexes that are not roots of uf) Pseudocode: For i = 1 to n uf.Find(i) size = Array(n) Initialize size to be...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT