In Java Lang

Submit the code with comments:

• Estimating g(x) Given f(x)
• Counting Operations to Produce Polynomials
• Demonstrating

If we can demonstrate this property by finding g(x) and a pair of witnesses c and k, then we have proven that our unknown function f(x) is a member of the set O(g(x)), where g(x) is a known reference function.

Reference Functions for g(x)

Countable Operations (Arithmetic, Relational, Logical, Assignment/Access)

{&,&&,|,||,!}

{=,[ ]}

Introduction

We are interested in recognizing a set of operations that can generalize well to multiple different hardware platforms. These operations invoke the ALU inside of the CPU and represent a basic computational step in a traditional load-store architecture (ie, a Von Neumann architecture). Lets put this into practice and count the number of operations that occur in a basic for loop.

/ote that int a = 0; occurs only once throughout the loop execution for(int a = 0; a  
Note that we are not concerned with the exact number of operations above, but rather, how does the number of operations change as we change n? If we double the input size, does the operation count double? Does it quadruple? Or does it change in some other way? Perhaps as n increases the operation count doesnt change at all, as well see in the first code example below  this is O(1). Well express the growth of the unknown function f(x) relative to functions we do know about, and try to get as close to f(x) as possible while also always being greater than f(x) past some value k.
 
Big O Reduction Rules
 
Asymptotic analysis is a useful tool for measuring complexity regardless of the specific hardware or platform being used. While a complex subject, there are a number of theorems that will help reduce the task of determining the reference function g(x) and the witnesses c and k. By making use of these reduction theorems, you can produce a polynomial for any arbitrarily complex code block. In general, well divide our code up into methods and examine those. These methods will provide terms that will contribute to our overall polynomial. Once weve produced a formula that corresponds to the code or method in question, well use the rules below to (1) reduce big o estimates and determine the most succinct g(x), c, and k.
 

• Addition Rule: If a segment of code a(x) is represented by the sum of two disjoint code sections f(x) and g(x), then the O(a(x)) is equal to the larger of the two : O(f(x)) or O(g(x))
  • Specifically,
  • In the example main below, foo() is and bar() is , so main is , and we can pick to be correspondingly. (The term becomes negligible as n moves to infinity, so the Big O is just the larger of the two terms.)

public static void main(String[] args) { foo(); //x^3 bar(); //x^2 } 

• Product Rule: If a segment of code is represented by the product of two (nested) code sections and ), then the is equal to the product of the two:
  • Specifically, O(a(x)) = O(f(x) * g(x))
  • In the example main() below, the function foo() is called n times, and inside foo(), we iterate over each of the n items. So foo() is O(n)and main calls foo() n times, resulting in O(nn)==O(n2).

public static void main(String[] args) { for(int a = 0; a  

• Log Exponent Rule: Consider the following logarithm . Note that we can rewrite this using the log roll as. Since constants are factored out during asymptotic analysis, you can simply drop the constant multiplier (which on a log is its exponent).
  • Example
    • f(x) becomes
• Log Base Rule: You may omit the base of the log and assume its base-2.
• Transitivity: if then . Related to big , if and Im trying to prove that a is less than or equal to (i.e, bounded by) ,we would write and find some pair of such that this relationship holds. Using transitivity,
  • 
  • 
  • 
    • Now simply choose c ==8 and k==1

Estimating g(x) Given f(x)

In the following section, indicate what reference function we should use when attempting to prove that is . Use the rules and reference functions above to guide you.

1. 
2. 
3. 
4. 
5. 
6. 

Counting Operations to Produce Polynomials

In the following section, I will present you with multiple different bodies of code, and it is your job to analyze each code section and build a polynomial that represents the number of abstract operations the code performs. Once were done here, well have built a polynomial that we will analyze further (in terms of , c, and k) in the next section. For the following code segments below, count the operations and produce a corresponding polynomial representation.

public static boolean isEmpty() { return head == null; } 

public static int num_occurrences(int n) { int count = 0; for(int i = 0; i  
 public static void c(int n) { //three loops for(int a = 0; a  
 
public static boolean isPrime(int n) { if(n == 1) return false; for(int i = 2; i  
Demonstrating | f(x) |  k
 
For each of the polynomials above, pick a reference function  and constants c,k such that the  bounds in the most succinct terms possible for Big O.
 
1. For the function isEmpty() above, what is ... 
 
 
 
 =
 
 
 
 
 
2. For the function num_occurences() above, what is...
 
 =
 
 =
 
 
 
 
 
3. For the function c() above, what is...
 
 
 
 =
 
  
 
 
 
4. For the function isPrime() above, what is...
 
 
 
 =
 
  
 
 
 
5. For your Bubble Sort, what is...
 
 
 
 =
 
 
 
 
 
6. For your Selection Sort, what is...
 
 
 
 =
 
  
 
 
<>