Блог пользователя Destopia

Confused about O(n) and O(1)
Автор Destopia, история, 7 лет назад, По-английски 
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?

  • Проголосовать: нравится
  • -14
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +14 Проголосовать: не нравится

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)$$$

→ Ответить
»
7 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить