CODEWITHSUNDEEP
algorithmbig-o
Mrfuzzy
Mrfuzzy

Reputation: 163

Complexity classes on faster computers

If an algorithm has a complexity class O(LogN) and solves a problem with N = 10^6 in 1 second on an old machine. How can I calculate the N solvable in the same time on a new machine 2x as fast?

I thought maybe I could calculate the constant which will be 1/log10^6 then use this to get the rest but I don't think this is right. can anyone guide me to the steps to solve this?

Thank you

Upvotes: 0

Views: 434

Answers (2)

Piyg
Piyg

Reputation: 244

Old machine: In time T, we have O(log N) cpu cycles.

New machine is 2x faster, so we have 0(2 log N) cpu cycles in same time T.

O(2 log N) = 0 (log N^2)

so we can effectively process N^2 data in the same time.

Upvotes: 1

user3386109
user3386109

Reputation: 34839

Let's assume that "Log" means log base 2. In that case "LogN" is 20. Which means the old machine was able to do 20 operations in 1 second.

The new machine can do twice as many operations, so that's 40 operations in 1 second. And that means that N = 2^40 is the value of N that the new machine can process in 1 second.

Upvotes: 0

Related Questions