Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Destopia's blog

Confused about O(n) and O(1)
By Destopia, history, 5 years ago, In English 
int n = 1000;
int cnt = 0;
for (int i = 0; i < n; i++)
   cnt++;

Is the above code O(n) or O(1)? Could anyone verify this?

  • Vote: I like it
  • -14
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

It's $$$O(n)$$$ and $$$O(1)$$$. $$$f(x)$$$ is $$$O(g(x))$$$ means there exist $$$c, n_0$$$ such that $$$\forall n \geq n_0$$$ $$$f(n) \leq cg(n)$$$

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

If you dont use n as a input and you assign n = 1000 that means the n-loops = constant so the time complexity of the code above is O(1). But if just the n-loops itself. It is O(n). So I think it is something like O(n = 1000) = O(1) complexity

Correct me if I am wrong

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There was a blog post on this topic two years ago.

→ Reply