Algorithms

Discussion in 'Engineering Concepts' started by Cleptography, Mar 21, 2011.

  1. Cleptography

    Cleptography New Member

    Joined:
    Sep 2, 2010
    Messages:
    39
    Likes Received:
    7
    Trophy Points:
    0
    Analyzing the efficiency of algorithms

    1 1 1 1 1
    e = --- + --- + --- + --- + --- + ...
    0! 1! 2! 3! 4!

    Code:
    public static void e1(int n) {
       double sum = 0.0;
       for (int i = 0; i < n; i++) {
          sum = sum + 1.0 / factorial(i);
       }
       System.out.println("e is approximately " + sum);
    }
    
    public static int factorial(int k) {
       int product = 1;
       for (int i = 1; i <= k; i++) {
          product = product * i;
       }
       return product;
    }
    Calculate total # of multiplications performed by e1(n):

    factorial requires k multiplications

    e1(n) requires 0 + 1 + 2 + ... + n-1 multiplications = ???

    +--+--+--+--+
    | |xx|xx|xx|
    +--+--+--+--+
    | | |xx|xx|
    +--+--+--+--+ n units
    | | | |xx|
    +--+--+--+--+
    | | | | |
    +--+--+--+--+
    n units

    number of blank squares = 1 + 2 + ... + n-1 + n
    + number of xx squares = 1 + 2 + ... + n-1
    -----------------------------------------------------
    = total number of squares = 2*(1 + 2 + ... + n-1) + n
    = n^2

    1 + 2 + ... + n-1 = (n^2 - n)/2 = 1/2 n^2 - 1/2 n

    So e1(n) requires 1/2 n^2 - 1/2 n multiplications in all

    Add count variable to e1 to see if theory agrees with practice

    "In theory there is no difference between theory and practice.
    In practice there is." --Yogi Berra

    n # muls = 1/2 n^2 - 1/2 n
    ----------------------------------
    0 0
    1 0
    2 1
    3 3
    4 6
    5 10
    6 15
    7 21
    8 28
    9 36
    10 45

    We could use other measures of running time, such as # of comparisons, # of
    additions, or total # of arithmetic operations:

    factorial(k):
    # loop cycles = k
    # multiplications = k
    # comparisons = k+1
    # additions = k
    # arithmetic operations = 2k

    e1(n):
    # loop cycles = n
    # multiplications = 1/2 n^2 - 1/2 n
    # comparisons = n+1 + [(0+1)+(1+1)+(2+1)+...+(n-1)+1] = 1/2 n^2 + 3/2 n + 1
    # additions = [0+1+2+...+(n-1)] + 2n = 1/2 n^2 + 3/2 n
    # arithmetic operations = #muls + #adds + #divs
    = 1/2 n^2 - 1/2 n + 1/2 n^2 + 3/2 n + n = n^2 + 2n

    Whichever measure we use, we still end up with an n^2 term.

    We say that the running time of e1 is "order n squared" or O(n^2)

    Now consider an alternative way of computing e:

    Code:
    public static void e2(int n) {
       double sum = 0.0;
       double denom = 1.0;
       for (int i = 1; i <= n; i++) {
          sum = sum + 1.0 / denom;
          denom = denom * i;
       }
       System.out.println("e is approximately " + sum);
    }
    # loop cycles = n
    # multiplications = n
    # comparisons = n+1
    # additions = 2n
    # arithmetic operations = #muls + #adds + #divs = n + 2n + n = 4n

    We say that the running time of e2(n) is "order n" or O(n)

    Examples
    O(1) = "constant time" 1, 6, 342, 5 trillion
    O(n) = "linear time" n, 3n+1, 40n + 5 trillion
    O(n^2) = "quadratic time" n^2, 1/100 n^2, 7n^2+3n+24
    O(n^3) = "cubic time" O(n^3): 100n^3+700n^2+1000
    O(log n) = "logarithmic time" binary search, fast exponentiation
    O(2^n) = "exponential time" lookahead in a game (show binary game tree)

    ====================================================================
    FAST EXPONENTIATION

    Code:
    public static double fastpower(double base, int n) {
       if (n == 1) {
          return base;
       } else if (even(n)) {
          return squared(fastpower(base, n / 2));
       } else {
          return base * fastpower(base, n - 1);
       }
    }
    Best case example: n=32
    32
    16
    8
    4
    2
    1

    5 multiplications
    log2(n) multiplications in the best case

    Worst case example: n=31
    31
    30
    15
    14
    7
    6
    3
    2
    1

    8 multiplications
    about 2 log2(n) multiplications in the worst case (2 floor[log2(n)] exactly)

    O(log n) time

    ====================================================================
    PRIME TESTING - How to determine if n is prime?

    Check all numbers 2, 3, 4, ..., n-1 to see if they divide n evenly

    Code:
    public static boolean primeTest1(int n) {
       if (n < 2) return false;
       for (int i = 2; i < n; i++) {
          if (n % i == 0) return false;
       }
       return true;
    }
    Worst case (when n is prime):
    n - 2 loop cycles
    1 + n - 1 + n - 2 = 2n - 2 total comparisons
    O(n) time

    -----------------------------------------------------------------------
    But no factors beyond n/2 exist, so we only need to check up to n/2
    Example: 24
    2 * 12
    3 * 8
    4 * 6
    6 * 4
    8 * 3
    12 * 2

    Code:
    public static boolean primeTest2(int n) {
       if (n < 2) return false;
       for (int i = 2; i <= n / 2; i++) {
          if (n % i == 0) return false;
       }
       return true;
    }
    Worst case:
    n/2 - 1 loop cycles
    1 + n/2 + n/2 - 1 = n total comparisons
    = O(n) time

    -----------------------------------------------------------------------
    But we only need to check up to sqrt(n) because of symmetry
    Example: 36 Example: 49
    2 * 18 7 * 7
    3 * 12
    4 * 9
    6 * 6
    9 * 4 redundant
    12 * 3 redundant
    18 * 2 redundant

    Code:
    public static boolean primeTest3(int n) {
       if (n < 2) return false;
       for (int i = 2; i * i <= n; i++) {
          if (n % i == 0) return false;
       }
       return true;
    }
    Worst case:
    sqrt(n) - 1 loop cycles
    1 + sqrt(n) + sqrt(n) - 1 = 2 sqrt(n) total comparisons
    O(sqrt n) time

    -----------------------------------------------------------------------
    But we don't need to check even numbers beyond 2

    Code:
    public static boolean primeTest4(int n) {
       if (n < 2) return false;
       if (n == 2) return true;
       if (n % 2 == 0) return false;
       for (int i = 3; i * i <= n; i += 2) {
          if (n % i == 0) return false;
       }
       return true;
    }
    Worst case:
    (sqrt(n)-1)/2 = 1/2 sqrt(n) - 1/2 loop cycles
    3 + (sqrt(n)-1)/2 + 1 + (sqrt(n)-1)/2 = sqrt(n) + 3 total comparisons
    O(sqrt n) time

    Loop cycles Comparisons Running time
    primeTest1 n - 2 2n - 2 O(n)
    primeTest2 n/2 - 1 n O(n)
    primeTest3 sqrt(n) - 1 2 sqrt(n) O(sqrt n)
    primeTest4 1/2 sqrt(n) - 1/2 sqrt(n) + 3 O(sqrt n)
     
    Last edited: Mar 21, 2011
    shabbir likes this.
  2. jhonackerman

    jhonackerman Banned

    Joined:
    Oct 13, 2011
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    hey! thanks for the helpful programming tips.
     
  3. sonamsharma

    sonamsharma New Member

    Joined:
    Jul 9, 2013
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    1
    Thanks for your helpful programming tip
     
  4. MarshallN

    MarshallN New Member

    Joined:
    Oct 25, 2016
    Messages:
    10
    Likes Received:
    1
    Trophy Points:
    3
    Gender:
    Male
    Thanks! Really usuful hint!
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice