Blog

Articles to grow your career

Article

Computing of the difficulty of the algorithm – Big O Notation

The complexity of algorithms is usually estimated by the execution time or by the memory used.
Asymptotic complexity is the complexity as the size of the input tends to infinity. The difficulty is usually described with the letter O. Examples:

  • O(1) – Constant Time Algorithms
  • O(n) – Linear Time Algorithms
  • O(log n) – Logarithmic Time Algorithms
  • O(n2) – Polynomial Time Algorithms
  • O(2^n) – Exponential Time Algorithms

Big O Rules:

  • Constants are ignored. For example:
  • 8n^4 =O(n^4)
    (n^2)/5=O(n^2)

  • In the expressions, only the fastest growing function is taken into account, because for very large n, only it will matter:
  • n^2+n=O(n^2)
    2^n+n^9=O(2^n)

  • The base of the logarithm is not written, since they differ by a constant: O(log()n).
Alex Kara
By Alex Kara on Apr 01, 2022
Coding tasks for interviews