Understanding Big O

Question

Given the following code, what is complexity 3. and how can I imagine simple algorithms with the following complexities?

O (N² + p)
O (N² + 2n)
O (LOGN) O (NlogN)

var collection = new[] {1,2,3}; var collection2 = new[] {1,2,3}; //1. //On foreach(var i in c1) { } //2. //On² foreach(var i in c1) { foreach(var j in c1) { } } //3. //O(nⁿ⁺ᵒ)? foreach(var i in c1) { foreach(var j in c2) { } } 

Answer 1

Outdoor foreach runs n = | c1 | times (where | x | is the size of c1 ), and the internal foreach is m = | c2 | time. This is O (n * m) times overall.

---

How can I imagine simple algorithms with the following complexities?

• O (N² + p)

This is the same as O (n ^ 2). What takes O (n ^ 2) time will drink a toast with every other person at the party, assuming there are exactly two people in the toast, and only one person makes the toast at a time.

• About (N² + 2n)

Same as above; O (n ^ 2) prevails. Another example of O (n ^ 2) effort is to plant trees in a square garden of length n , assuming that each tree needs constant time to plant, and when you plant a tree, other trees are excluded from its surroundings.

• About (LOGN)

An example of this would be to search for a word in a dictionary by repeatedly selecting the middle of the page area to search in the following. (In other words, binary search.)

• About (NlogN)

Use the algorithm above, but now you need to find every word in the dictionary.

Answer 2

3 - O (n * m), or O (n ^ 2) if two collections are the same size.

O (n ^ 2 + n) does not make sense, since n is less than n ^ 2. Just write O (n ^ 2).

The most worthy sorting sorting algorithms work in O (n * log (n)). If you don't know anything, look at Wikipedia.

A binary search is O (log (n)).

Answer 3

No O (n² + n) or O (n ^ 2 + 2n). Leaving aside most of the mathematical foundations of algorithmic complexity, you should at least know that this is an "asymptotic behavior." As N approaches infinity, the term n ^ 2 dominates in the value n ^ 2 + n, so this is the asymptotic complexity of n ^ 2 + n.

3 complexity - O (I * J), where I and J are the size of the inputs in c1 and c2.

Answer 4

In truth, O (n² + n) and O (n² + 2n) are the same.

Answer 5

Complexity 3 is O (m * n). There is no complexity O (n ² + n) or O (n ² + 2n). It is just O (n ² ). This is because n is o (n ² ).

Example O (log (n)) - binary search.

Example O (n * log (n)) is a merge sort.