Difference between revisions of "CIS 3020 Part 7"

From In The Wings
Jump to navigation Jump to search
Line 90: Line 90:
 
* And, even if it is O(log N), it will be slower than the first method
 
* And, even if it is O(log N), it will be slower than the first method
 
* Let's look at values to see if this is true...
 
* Let's look at values to see if this is true...
 +
{| border="1"
 +
!N!!O(N)!!O(log N)!!39*O(N)!!143*O(log N)
 +
|-
 +
|2|2|1|78|143
 +
|-
 +
|4|4|2|156|286
 +
|-
 +
|8|8|3|312|429
 +
|-
 +
|16|16|4|624|572
 +
|-
 +
|32|32|5|1248|715
 +
|-
 +
|64|64|6|2496|858
 +
|-
 +
|128|128|7|4992|1001
 +
|-
 +
|256|256|8|9984|1144
 +
|-
 +
|512|512|9|19968|1287
 +
|-
 +
|1024|1024|10|39936|1430
 +
|}
 +
==String Reversal==

Revision as of 11:23, 26 April 2007

Complexity

  • When computing O(), we are concerned with big values of n
  • With big values, constants become ignorable
  • Consider the two exponential functions we developed
  • Let's count all operations (arithmetic, assignment, references, comparisons, etc.) the same with calls counting 20.

Exponentiation, O(N)

public int expt(int b, int n) {
  int result;
  if (n<=0) {
    result = 1;
  } else {
    result = b * expt(b, n-1);
  }
  return result;
}


2
1
3
3

28

2
------
39

Exponentiation, O(log N)

public int expt(int b, int n) {
  return fastExpt(b,n);
}

private int fastExpt(int b, int n) {
  int result;
  if (n<=0) result = 1;
  else if (even(n)) result = square(fastExpt(b, n/2));
    else result = b * fastExpt(b, n-1);
  return result;
}

private int square(int x) {
  return (x * x);
}

private boolean even(int x) {
  return (x % 2 == 0);
}


2
23


2
1
6
67
28
2


1
4


1
6
------
143

Comparison

  • some might argue that the second method is ~3.7 times as expensive
  • And, even if it is O(log N), it will be slower than the first method
  • Let's look at values to see if this is true...
N O(N) O(log N) 39*O(N) 143*O(log N)
2|1|78|143
4|2|156|286
8|3|312|429
16|4|624|572
32|5|1248|715
64|6|2496|858
128|7|4992|1001
256|8|9984|1144
512|9|19968|1287
1024|10|39936|1430

String Reversal

Retrieved from "https://wiki.inthewings.net/index.php?title=CIS_3020_Part_7&oldid=2116"