# Calculating time for algorithm

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

#### Nforce

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

• 1 person

#### HallsofIvy

MHF Helper
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.

• 1 person

#### Nforce

Very clear, thanks.