I really cannot make it clearer that I'm nitpicking on the statement that it is "sublinear". I'm not disagreeing that it's O(log(n)). I'm also not disagreeing that it's "sublinear with respect to n". I'm disagreeing with it being "sublinear", because there are at least 2 meanings that come to my mind:
1. "it's sublinear with respect to n" - this is true
2. "it's sublinear with respect to size of the input" - this is false
I do not know how else to explain this to you that it is the size of the input that matters when talking about complexity. Example quora answer that recognizes the distinction (discussions about the technicality in the naive isPrime impl that checks numbers from 2 to sqrt(n)): https://qr.ae/pGuORe.
I do not know how else to explain this to you that it is the size of the input that matters when talking about complexity. Example quora answer that recognizes the distinction (discussions about the technicality in the naive isPrime impl that checks numbers from 2 to sqrt(n)): https://qr.ae/pGuORe.