1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combine algorithms question

  1. Nov 2, 2013 #1
    *solved

    1. The problem statement, all variables and given/known data

    Lets say we have three algorithms, which include the following complexities 200n, 3n^2, 2^n-1. What would be a combined algorithm which is efficient?

    2. Relevant equations



    3. The attempt at a solution

    Let me know if I'm on the right path here.

    100n+3n^2 + 2^(n-1)
    =log(100n)+log(3n^2)+log(2^(n-1))
    =[log(100) + log(n)]+[log(3)+log(n^2)]+[(n-1)*log(2)]
    =[log(100) + log(n)]+log(n^2)+(n-1),exclude constants
    =log(n)+2log(n)+n
    =(3log(n)+n)

    The efficiency of the combined algorithm is O(3log(n)).
     
    Last edited by a moderator: Nov 2, 2013
  2. jcsd
  3. Nov 2, 2013 #2

    gneill

    User Avatar

    Staff: Mentor

    I'm not sure about the logic behind your derivation. Adding together the Orders of different algorithms doesn't make sense to me. Also, in the second line, why have you taken term-by-term logs? The second line won't equal the first.

    I could be wrong, but when I look at the problem as stated I imagine that the idea would be to have the program select, based upon the value of n, the algorithm which would minimize the run time. Then you would have different complexities for different ranges of n. The problem would then be to work out the ranges of n that suit each algorithm.
     
  4. Nov 2, 2013 #3
    I think it is asking for what values of N is Alg(X) the fastest.

    Naively, for what values of n (n>=0) is alg(1) < alg(2), alg(2)<alg(1), alg(2)<alg(3), alg (3)<alg(2), alg(3)<alg(1), alg(1)<alg3).
    Then just select the best minima.

    Starting with, for what vales of n does 200n - 3n^2 = 0
     
  5. Nov 2, 2013 #4

    Mark44

    Staff: Mentor

    We don't ordinarily delete the contents of threads when they're solved. Other people can sometimes benefit from them.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combine algorithms question
Loading...