Calculating time for algorithm

Mar 2010
224
2
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}\)?
 
Mar 2010
224
2
Sorry but this should be easy for you mathematicians. I don't have the answer, so my question is if it's correct?

Thanks.
 

SlipEternal

MHF Helper
Nov 2010
3,728
1,571
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.
 
  • Like
Reactions: 1 person

HallsofIvy

MHF Helper
Apr 2005
20,249
7,909
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.
 
  • Like
Reactions: 1 person