CODEWITHSUNDEEP
pythonbig-ocomplexity-theory
Jason Lee Eaton
Jason Lee Eaton

Reputation: 178

big O that is less than N?

Being completely self (and StackOverflow) taught, I'm new to Big-O notation and need to understand it better for some upcoming interviews.

My question is how do you annotate in Big-O when the complexity is less than N? Example is a prime calculator that checks for remainder of every integer up to N/2, since if we find no divisor less than half, it's certain there will be none in the upper half.

So is that O(N/2) or does N become N = N/2 for the purposes of the notation?

def primecheck(num):
  i = 2
  while i <= ( num // 2 ):
    if not (num % i):
      return False
    i += 1
  return True

Upvotes: 1

Views: 148

Answers (2)

Ruli
Ruli

Reputation: 2780

Big-O notation is designed to express variable-only complexity, all constants are ignored in this case so n/2 is expressed same as 4n. However prime numbers checking is a problem that needs to check only up to sqrt(n) so the problem is just O(sqrt(n))

Upvotes: 1

chepner
chepner

Reputation: 531055

Big-O notation is designed to ignore constant factors. As long as k is a constant (meaning, something unrelated to N, such as 1/2, 1/3, 1, 2, 3, etc), then O(kN) means exactly the same thing as O(N).

Upvotes: 3

Related Questions