Computer scienceAlgorithms and Data StructuresIntro to algorithms and data structuresUnderstanding algorithms and complexity analysis

Big O: how to count it

Theory

Time complexity

Report a typo

Suppose you need to solve a task. It's possible that this task can be solved with several different algorithms (or combinations thereof). Some algorithms can have higher time complexity (i.e. less efficient) and some can have lower time complexity (i.e. highly efficient) in comparison.

Now, suppose you choose an algorithm with time complexity $O(n)$ , to create your own algorithm to solve this task. And for that, you used that $O(n)$ algorithm total $\frac{n}{2}$ times. Choose the lowest possible estimate of time complexity.

Tip: While time complexity calculations, we focus solely on the behavior of our algorithm with large input sizes. Therefore, repeating some steps a constant number of times does not affect the complexity i.e. constants can be ignored.

Select one option from the list

O(n)

O(n*\log n)

O(n*\sqrt{n})

O(n^2)

___

Create a free account to access the full topic