# Tag Info

67

O(n) + O(n log(n)) = O(n log(n)) For Big O complexity, all you care about is the dominant term. n log(n) dominates n so that's the only term that you care about.

60

"N log N" is as good as you're going to get, and should be well understood by professional programmers. You can't expect there to be a single word to describe every complexity class that exists.

57

Let's reason our way through it and remember the definition of O. The one I'm going to use is for the limit at infinity. You are correct in stating that you perform two operations with corresponding asymptotic bounds of O(n) and O(nlog(n)) but combining them into a single bound is not as simple as adding the two functions. You know your function takes at ...

53

Are there any practical considerations that I am overlooking which making binary search better than linear search? Yes - you have to do the O(n log n) sorting only once, and then you can do the O(log n) binary search as often as you want, whereas linear search is O(n) every time. Of course, this is only an advantage if you actually do multiple searches on ...

50

There is a jargon term linearithmic meaning exactly this. I don't believe that it's universally understood by all programmers, so if you're not careful then it will obscure more than it informs. Personally I don't normally use it, and if I did then I'd probably define it on first use, for example "this article considers linearithmic (O(N log N)) algorithms"....

49

It does make sense to me that this makes it faster to solve a problem if the two halves takes less than half the work of dealing with the whole data set. That is not the essence of divide-and-conquer algorithms. Usually the point is that the algorithms cannot "deal with the whole data set" at all. Instead, it is divided into pieces that are trivial to solve ...

23

There are several reasons, but probably the most important one is that constants are a function of the implementation of the algorithm, not the algorithm itself. The order of an algorithm is useful for comparing algorithms irrespective of their implementation. The actual runtime of a quicksort will typically change if it's implemented in C or Python or ...

22

With small n Big O it is just about useless and it's the hidden constants or even actual implementation that will more likely be the deciding factor for which algorithm is better. This is why most sorting functions in standard libraries will switch to a faster insertion sort for those last 5 elements. The only way to figure out which one will be better is ...

22

O(n) and other order notation is (typically) not concerned with the behavior of functions for small values. It is concerned with the behavior of functions for very large values, namely limits as n moves toward infinity. The constants technically matter but they are typically abstracted away as once n becomes large enough, c's value is entirely irrelevant. ...

19

The complexity class is O(n²). Visual explanation Imagine a n·n square which lists all the values j takes on. We remove the diagonal (which has n entries) and the upper right half because j will never be larger or equal to i. We are then left with an area of (n² - n)/2. i | values of j | no of j values ----+-----------------+--------------- 0 | · ·...

19

If this wasn't an assignment, you could relatively easily guess which one of the solutions is better here. In most cases, it would be the first one. In some rare cases (and the fact that you're talking about the financial sector means that you shouldn't ignore this possibility), performance would be key (either because the piece of code will be run hundreds ...

17

This is an interesting question. Fortunately, once you know how to solve it, it is not particularly hard. For functions f: N → R+ and g: N → R+, we have f ∈ O(g) if and only if lim supn→∞ f(n) / g(n) ∈ R. A function f: N → R+ has at most polynomial growth if and only if there exists a constant k ∈...

16

There is no fundamental difference. The function map has O(n) complexity, because it iterates over a list of size n and applies an operation to each element. The loop which is explicit in your first example just happens inside the map function. A typical implementation of map could be: map f [] = [] map f (x:xs) = f x : map f xs Here it is easy to see ...

14

The basic assumption is that you do not make one search. So if you need to search the same data multiple times then you only have to sort once and can profit from binary search. If you a searching often and have changing data it is worth to use a sorted list where new entries are sorted into the list. So basically binary search is better when you search ...

14

No, O(log n) + O(log n) is not O(n). It is still O(log n). When we have a big-O formula multiplied by a constant, it is equivalent to the value without the multiplied constant. So: O(k * g) = O(g) where k is a constant, non-zero factor and g is a bounding function. An O(log n) operation is an operation that takes a number of steps proportional to the ...

13

It is sometimes called "loglinear", although that word actually means something different. I would just stick with "N log N", though, as @Philip's answer suggests.

11

Complexity classes such as O(n) or O(n²) are not meant to calculate actual running time. Instead, they are meant to compare how different algorithms scale when we change the input size. For example, here we have two algorithms that apply frobnicate(a, b) to each matching item: void algorithm1(Set<int> items) { for (int i in items) { for (int j ...

10

Big O notation as per definition states that: For a given function g(n), we denote by O(g(n)) the set of functions: O(g(n)) = {f(n): there exist positive constants c and n' such that 0<=f(n)<=c.g(n) for all n > n'} The Big O notation is built on the intuition that for all values n at and to the right of n', the value of f(n) is on or below c.g(n). ...

9

In algorithm analysis, Order of Growth is the key abstraction and it gives the rate at which the running time changes as the input size changes. Let's say an algorithm has a running time f(n) = 2n + 3. Now we plug in some input size, n = 10: 2 * 10 + 3 = 23 n = 100: 2 * 100 + 3 = 203 n = 10000: 2 * 10000 + 3 = 20003 n = 1000000: 2 * 1000000 + 3 = 2000003 ...

9

Very meaningful in my experience. At the root of many performance problems I often find these causes... Failure to consider the range of n for which the algorithm will be used. Failure to consider time complexity of the algorithm used. Failure to consider memory requirements of the alogrithm for the likely range of n. Failure to consider latency differences ...

9

First things first, OOD isn't something you can approach systematically. There's no checkboxes for something that will vary based on who is doing it and what environment you're in. So your assumption that efficiency will follow a similar path is flawed. In practice, very few companies care very much about efficient code. Those blurbs are (very often) put in ...

8

For a proof of completeness, it is not necessary to look specificially at A*. Any finite graph search algorithm using a node queue where you take one element from, generate all children of that graph node and put them back into the queue is complete, "A*" is just a special case of that kind of algorithms. Once you got this, it is easy to find a proof of ...

8

In this specific case, you can replace the variables with their minimum and maximum values to find the number of steps for each loop. The first loop goes from 0 to n, the second loop goes from 0 to n*n and the inner loop goes from 0 to n*n. So there are n2 iterations of the innermost loop, times n2 iterations of the second loop, times n iterations of the ...

8

You seem to be confusing the median value and the middle element. The middle element of the unsorted array could indeed turn out to be close to the lowest or highest value. The median value on the other hand is the value that has half the values compare as smaller and half the values compare as bigger. The advantage of using the median value as a pivot in ...

7

because once you have a sorted list you don't need to re-sort it each time which means that if you have more than O(log n) searches sorting in advance will net you a gain win (O(n log n + k log n) vs O(k*n)

7

The cost function C for quicksort consists of two parts. The first part is the cost of partitioning the array in two 'halves' (the halves don't have to be of equal size, hence the quotes). The second part is the cost of sorting those two halves. The (N + 1) term is actually a condensed term, and comes from the terms (N - 1) + 2 This is the cost of the ...

7

Big O notation is absolutely relevant for any program which will be executed on physical hardware. As an example, Clojure is a functional programming language, and its own documentation lists the Big O notation for operations on its data structures (particularly the collections - list, vector, and map). Knowing the Big O factors for each collection will ...

7

As already mentioned by @Dipstick, step 3 can fail if there are duplicates in the input array. To resolve this and improve the time complexity, one can use a dictionary with the array elements as keys and their number of occurrence as values. Such a dictionary can be created from the sorted and the unsorted array as well in O(n), and you need to test if the ...

Only top voted, non community-wiki answers of a minimum length are eligible