this is the algorithm :

F() = {
  count = 0
  n = 1000
  For i = 1 to n Do
   If n Modulo i = 0 Then
     count = count + 1
   end if
  end for
  if count = 2 then
   return prime
  else return prime

So what i know is complexity of a loop is n and other than loop is some constant

so what i get is O(n)

but my teacher said its O(1) because the n is already defined

is my teacher correct ?

Thank you in advance :) Sorry for my bad english

  • $\begingroup$ (Sorry for my bad english Prefer getting help, if by a machine, over begging for leeway: Let a spelling checker assist you. For text decoration, see the post editor help.) (When communicating for a purpose, investing appropriate effort should suffice. Never mind perfection (unless you're a professional writer using your 1st language).) $\endgroup$
    – greybeard
    Oct 4 at 8:26

Your teacher is correct. We measure the complexity with respect to the input's size.

Here, you don't have any input to the function, and $n$ is just a constant defined within the function.

Thus, the loop runs only a constant number of times, which is $O(1)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.