Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

overwrite's blog

By overwrite, history, 2 weeks ago, In English,

If a program always makes one million steps to execute, then what is its time complexity? maybe O(1)?

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

O(1000000)

»
2 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Ofc O(1)

»
2 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Its O(10^7)

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For your own sake, go and read some foundation Computer Science notes relating to computational complexity. I am pretty sure you didn't understand the definition of Big O.

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I know that it's a constant. But asked it to get some upvotes, cause that's a good question for beginners :v

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Remember a function $$$f$$$ is $$$O(g(n))$$$ if and only if there exist positive constants $$$c$$$ and $$$m$$$ such that $$$0 \leq f(n) \leq cg(n)$$$ for all $$$n \geq m$$$.

In the case you present, $$$f(n) = 1000000$$$ for all positive $$$n$$$, so guessing $$$g(n) = 1$$$, if $$$c \geq 1000000$$$ and $$$m$$$ is a positive integer, we have $$$0 \leq f(n) = 1000000 \leq cg(n)$$$ (remember $$$cg(n) \geq 1000000*1 = 1000000$$$).

Thus, is proven $$$f(n) = 1000000 = O(1)$$$.