HNGlance

Top Best New Show

Teaching Kids Programming

https://github.com/DoctorLai/Teaching-Kids-Programming/blob/main/README.md

by justyy • 6 years ago

2 1 6 years ago

GI

Related Stories

Loading related stories...

Comments

1

ColinWright• 6 years ago

Following one of the links, I get to the blog page on algorithmic complexity. There it says:

O(Sqrt(N))
Checking if a number is a prime number runs at O(Sqrt(N)) because we can just check the possible factors from 2 to Sqrt(N) to see if it can be divided.

This is completely at odds with the usual definition, where we talk about the size of an instance in terms of the number of bits needed to specify the instance. So given the instance, the number N, the size of the problem, S, is log_2(N). The number of trial divisions is then proportional to sqrt(N), but we need to express that in terms of S.

S=log_2(N), so N=2^S, and sqrt(N)=2^(S/2) ~ (1.4)^S. That means the time taken is proportional to (1.4)^S, and this algorithm is exponential.

Source preview

github.com

HNGlance

© 2024-2026 HN Glance. Story content belongs to its original sources.

Privacy
Terms