Thread: dynamic programming

  1. #1
    Banned
    Join Date
    Apr 2015
    Posts
    596

    dynamic programming

    Hi guys, what's up?
    I would like to ask whenever I have replicated recursive call (meaning the same recursive call called for instance twice), why the time complexity of it is bigger than the time complexity if we do a recursive call in a dynamic programming(meaning having an array and storing the called recursive call to read it again if being called)

    ** intuitive if we are not having an array to store the replicated recursive call then implicitly I must do double work (double time) to get the data unlike if I have an array that's already stored my data ....but how would I know that the time for getting data from array is lesser than having a recursive call?! ***

    In other words, why eliminating replicated recursive call is mandatory for decreasing the time complexity?!

    thanks guys!
    Last edited by RyanC; 12-21-2018 at 09:52 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by RyanC
    but how would I know that the time for getting data from array is lesser than having a recursive call
    Arrays are regarded as having random access, i.e., accessing an element of an array by index is regarded as taking constant time.

    In reality it can be more complex than that, but complexity analysis (ironically?) simplifies that complexity. If you really need to know in practice, measure the timings with typical test data.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Dec 2018
    Posts
    38
    Quote Originally Posted by laserlight View Post
    If you really need to know in practice, measure the timings with typical test data.
    But that would require that he actually writes a program, something I've never see him do! He just asks strange, usually totally obvious, questions.

  4. #4
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by laserlight View Post
    Arrays are regarded as having random access, i.e., accessing an element of an array by index is regarded as taking constant time.

    In reality it can be more complex than that, but complexity analysis (ironically?) simplifies that complexity. If you really need to know in practice, measure the timings with typical test data.
    Got you, and you mean by constant time which PC can get implicitly the data faster than a recursive way ye?! thanks

  5. #5
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by bruteforce View Post
    But that would require that he actually writes a program, something I've never see him do! He just asks strange, usually totally obvious, questions.
    Excuse me? I guess that my question on point, secondly the forum isn't for writing my code over but it's helping what's bugging you while coding/writing code. thanks for your comment btw.
    thirdly, when you're coding something it's more amazing if you know about how optimal(int terms of time) your code is !
    Last edited by RyanC; 12-21-2018 at 12:35 PM.

  6. #6
    Registered User
    Join Date
    Dec 2018
    Posts
    38
    Quote Originally Posted by RyanC View Post
    Excuse me? I guess that my question on point, secondly the forum isn't for writing my code over but it's helping what's bugging you while coding/writing code. thanks for your comment btw.
    thirdly, when you're coding something it's more amazing if you know about how optimal(int terms of time) your code is !
    Excuse you? There is no excuse for you! You sound like a total moron to me, and to most other people here by the looks of it. Try actually writing a program some day!!!

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by RyanC
    and you mean by constant time which PC can get implicitly the data faster than a recursive way ye?
    No, that's not what constant time means. You asked a question about time complexity, so either you have already read up on what constant time means, or you need to do so rather than be spoonfed.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dynamic Programming
    By niconistal in forum C++ Programming
    Replies: 2
    Last Post: 08-04-2010, 12:45 AM
  2. Who knows dynamic programming in c ?
    By urpis in forum C Programming
    Replies: 2
    Last Post: 05-10-2010, 03:42 PM
  3. Dynamic Programming
    By iamnew in forum C++ Programming
    Replies: 2
    Last Post: 05-08-2010, 05:25 AM
  4. Dynamic Programming
    By sshd in forum C Programming
    Replies: 3
    Last Post: 11-14-2007, 11:21 AM
  5. dynamic programming help
    By twigboy in forum C++ Programming
    Replies: 2
    Last Post: 02-03-2005, 09:29 PM

Tags for this Thread