1. Engineering
  2. Computer Science
  3. question 01 complexity analysis consider the following method one public...

Question: question 01 complexity analysis consider the following method one public...

Question details

Question 01: Complexity Analysis

Consider the following method one.

public static int one(int n){

      int x = 0;

      for(int i=n*n; i > 0; i/=2){

          if(i < n )  

             x += two(i); //statement 1

          else for(int j= i; j<=i; j++)

              x += i*j;

          x += three(i);

      }

      return x;

}

    public static int two(int n){

         int x = 0;

      for(int i = n; i > n / 2; i--)

          x ++; //statement 2

      return n+x;

  }

    public static int three(int n){

          int x = 0;

       for(int i = 1; i < 500 ; i*=2)

           x ++; //statement 3

       return n+x;  

   }

It is assumed that each simple instruction such as addition, multiplication, division, comparison and assignment is O(1).

  

  1. Count the number of times statement1, statement2and statement3get executed in terms of the input number n.
  2. Express the overall cost of method one as a function f(n), where nis the problem size, by finding the cost of the most expensive operation. Clearly indicate that most expensive operation.
  3. Determine the Big-O() time complexity of method one.
Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution