CIS 3020 Part 5

Messy Example 1

Code

ass Mess1 {
  public static void main (String[] arg) {
    int d;
    d=10;
    System.out.println(d);
    Ex1 g;
    g=new Ex1();
    g.a(d);
    System.out.println(d);
  }
}

class Ex1 {
  int p;
  
  Ex1() {
    p=0;
  }
  
  public void a (int p) {
    this.b(p);
    this.printVals(p);
    this.b(this.p);
  }

  private void b (int q) {
    this.printVals(q);
  }

  private void printVals(int r) {
    System.out.println(r);
  }
}

Output

10
10
10
0
10

Messy Example 2

Code

class Mess2 {
  public static void main (String[] arg) {
    int d,e;
    d=4;
    e=6;
    System.out.println(d + " " + e);
    Ex2 g = new Ex2();
    g.a(d,e);
    System.out.println(d + " " + e);
  }
}

class Ex2 {
  int p;
  
  Ex2() {
    p=3;
  }
  
  public void a (int p, int r) {
    this.b(r,p);
    this.printVals(p,r);
    this.b(this.p,r);
  }

  private void b (int p, int r) {
    this.printVals(p,r);
    this.printVals(this.p,r);
  }

  private void printVals(int p, int r) {
    System.out.println(p + " " + r);
  }
}

Output

4 6
6 4
3 4
4 6
6 3
3 3
4 6

Messy Example 3

Code

class Mess3 {
  public static void main (String[] arg) {
    int d,e;
    d=4; e=6;
    System.out.println(d + " " + e);
    Ex3 g = new Ex3();
    g.a(d,e);
    System.out.println(d + " " + e);
  }
}

class Ex3 {
  int p;
  
  Ex3() {
    p=3;
  }
  
  public void a (int p, int r) {
    this.b(r,p);
    this.printVals(p,r);
    this.b(r,this.p);
  }

  private void b (int p, int r) {
    this.printVals(r, this.p);
    c(p,r);
    c(this.p, r);
  }

  void c(int r, int p) {
    this.printVals(p,r);
  }

  private void printVals(int p, int r) {
    System.out.println(p + " " + r);
  }
}

Messy Example 4

Code

class Mess4 {
  public static void main (String[] arg) {
    int d,e,f;
    d=4; e=6; f=8;
    System.out.println(d + " " + e + " " + f);
    Ex4 g = new Ex4();
    g.a(d,e,f);
    System.out.println(d + " " + e + " " + f);
  }
}

class Ex4 {
  int p;
  Ex4() {
    p=3;
  }
  
  public void a (int p, int q, int r) {
    b(q,r,p);
    this.printVals(p,q,r);
    this.b(r,q,this.p);
  }

  private void b(int p, int q, int r) {
    this.printVals(p,q,r);
    c(this.p, q, r);
    c(p,r,q);
  }

  void c(int q, int p, int r) {
    this.printVals(p,q,r);
  }

  private void printVals(int p, int q, int r) {
    System.out.println(p + " " + q + " " + r);
  }
}

Tree Recursion

• Consider the Fibonacci Number Sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

• This sequence is defined by the rule:

        /  0                     when n=0
fib(n)= |  1                     when n=1
        \  fib(n-1) + fib(n-2)   otherwise

• As code this is:

public int fib (int n) {
  int result;
  if (n<=0)
    result = 0;
  else if (n == 1)
    result = 1;
  else 
    result = (fib(n-1) + fib(n-2));
  return result;
}

Orders of Growth

• An important consideration in the comparison of different soluytions to problems is the complexity of the algorithms used.
• This complexity is measured on two important quantities:
  • The space requirements (space complexity) to represent all values used in the algorithm
  • The time requirements (time complexity) needed to perform all of the needed calculations

The BIG-O

Informal Definition

If function Est(n) times some integer constant, m, dominates funciton Time(n), then we say:

Time(n) = O(Est(n))

Algebraic Identities for Big-O

Assume c denotes a constant and that f and g are arbitrary functions

1. c * f = O(f) -- you can drop constant multipliers

17n = O(n)

25n² = O(n²)

99 = O(1)

2. f + g = O(f), so long as f dominates g

n² + 3 = O(n²)

n5 + n3 + n = O(n5)

3. f * g = O(f) * O(g)

n3m² = O(n3) * O(m²)

Important Order Relationships

for the following assume that k and c are positive constants and that n is a variable

nn	dominates n!
n!	dominates cn
cn	dominates kn, so long as c>k
kn	dominates kc, so long as k>1
nc	dominates nk, so long as c>k
n2	dominates n * log(n)
n * log(n)	dominates n
n	dominates log(n)
log(n)	dominates 1

Special Big-O Complexities

• A complexity of O(1) is called Constant Complexity
• A complexity of O(N) is called Linear Complexity
• A complexity of O(N^K) is called Polynomial Complexity
• Any complexity dominating O(2^N) is called Exponential Complexity

Growth of Complexity Functions

log(n)	n	n * log(n)	n2	n3	2n
0	1	0	1	1	2
1	2	2	4	8	4
2	4	8	16	64	16
3	8	24	64	512	256
4	16	64	256	4096	65536
5	32	160	1024	32768	4294967296
6	64	384	4096	262144	(Note 1)
7	128	896	16384	2097152	(Note 2)
8	256	2048	65536	16777216	?????

1. Approximately the number of machine instructions executed on a 1 gigaflop (10⁹) supercomputer in 5000 years.
2. Approximately 500 billion times the age of the universe (in nanoseconds: 10^-9)