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, ,

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

• +11

 » 2 weeks ago, # |   +3 O(1000000)
 » 2 weeks ago, # |   +16 Ofc O(1)
 » 2 weeks ago, # |   -19 Its O(10^7)
•  » » 13 days ago, # ^ |   -11 sorry, its O(10^6)
 » 13 days ago, # |   0 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 →   0 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, # |   0 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)$.