# Thread: Calculating time for algorithm

1. ## 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}$?

2. ## 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.

3. ## Re: Calculating time for algorithm

Originally Posted by Nforce
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.

4. ## 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.

5. ## Re: Calculating time for algorithm

Very clear, thanks.