Results 1 to 2 of 2

Math Help - Algorithms

  1. #1
    Member
    Joined
    Oct 2008
    Posts
    130

    Algorithms

    Show that an algorithm that makes at most a constant number of calls to polynomial time subroutines runs in polynomial time, but that a polynomial number of calls to polynomial-time subroutines may result in an exponential time algorithm.

    For the first part, can I say that the algorithm runs in O(x^m) where x^m is the longest run time of all the subroutines?

    I have no idea for part 2
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Dec 2009
    Posts
    4
    For the first question you answer is correct. About this second you have to notice that if your program performs a_kx^k + ... + a_0 operations, its lower and upper bound is cx^{k+1} (think why?). So if number of executed subroutines is constant, maximal k will always be constant (assuming it depends on number of executions, but I think that's what the task is about, becuse if complexity of execution of one subroutine is indepentant, then it will be only product of two polnynominals, so polnynominal), but otherwise (polynominal number of executions) it can rise to the number of exections, which is polynominal, so we will get complexity like \Theta(n^{p(n)}), where p(n) is a polynominal.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithms
    Posted in the Math Software Forum
    Replies: 2
    Last Post: November 4th 2010, 09:25 PM
  2. Algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 8th 2010, 10:48 PM
  3. algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 16th 2010, 03:25 PM
  4. Algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 17th 2009, 08:11 AM
  5. Algorithms
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2009, 12:33 PM

Search Tags


/mathhelpforum @mathhelpforum