Results 1 to 5 of 5
Like Tree2Thanks
  • 1 Post By SlipEternal
  • 1 Post By HallsofIvy

Thread: Calculating time for algorithm

  1. #1
    Member
    Joined
    Mar 2010
    Posts
    202

    Lightbulb Calculating time for algorithm

    If we have algorithm $\displaystyle A$ with time complexity: $\displaystyle N^2$ and algorithm $\displaystyle B$ which does the same thing but with time complexity of $\displaystyle N\log_2{N}$

    If $\displaystyle N = 5000$ and algorithm $\displaystyle A$ takes 10 seconds to solve the problem, how much time (in seconds) would algorithm $\displaystyle B$ take?

    Is my solution correct: $\displaystyle 10\frac{5000\log_2{5000}}{5000^2}$?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2010
    Posts
    202

    Re: Calculating time for algorithm

    Sorry but this should be easy for you mathematicians. I don't have the answer, so my question is if it's correct?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,728
    Thanks
    1521

    Re: Calculating time for algorithm

    Quote Originally Posted by Nforce View Post
    If we have algorithm $\displaystyle A$ with time complexity: $\displaystyle N^2$ and algorithm $\displaystyle B$ which does the same thing but with time complexity of $\displaystyle N\log_2{N}$

    If $\displaystyle N = 5000$ and algorithm $\displaystyle A$ takes 10 seconds to solve the problem, how much time (in seconds) would algorithm $\displaystyle B$ take?

    Is my solution correct: $\displaystyle 10\frac{5000\log_2{5000}}{5000^2}$?
    Not necessarily.

    $O(N\log_2 N), O(N^2)$ may have different constant factors. You are treating them as having the same constant factor.
    Thanks from Nforce
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    20,046
    Thanks
    3174

    Re: Calculating time for algorithm

    Saying that algorithm A has time complexity $\displaystyle N^2$ means that the time is $\displaystyle A= \alpha N^2$ for some constant $\displaystyle \alpha$. Saying further that A= 1000 when N= 5000 means that $\displaystyle 1000= 25000000\alpha$ so that $\displaystyle \alpha= \frac{1000}{25000000}=\frac{1}{25000}$. Saying that algorithm B has time complexity $\displaystyle N log_2(N)$ means that $\displaystyle B= \beta N log_2(N)$ for some constant $\displaystyle \beta$. As SlipEternal said, $\displaystyle \beta$ is not necessarily the same as $\displaystyle \alpha$ so the time algorithm A takes says nothing about the time algorithm B takes.
    Thanks from Nforce
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2010
    Posts
    202

    Re: Calculating time for algorithm

    Very clear, thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Expanded Euclidean Algorithm (calculating r and s)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 7th 2018, 08:48 PM
  2. Replies: 5
    Last Post: Jan 17th 2013, 01:32 AM
  3. Fast algorithm for calculating permutations
    Posted in the Statistics Forum
    Replies: 1
    Last Post: Dec 1st 2010, 09:13 PM
  4. average time for recursive algorithm
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: Dec 24th 2008, 07:59 AM
  5. sorting fraction with linear time algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 11th 2008, 09:39 PM

Search tags for this page

Click on a term to search for related topics.

/mathhelpforum @mathhelpforum