Hot answers tagged

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.


63

It's O(n * log(n)), not O(log(n)). As you've accurately surmised, the entire input must be iterated through, and this must occur O(log(n)) times (the input can only be halved O(log(n)) times). n items iterated log(n) times gives O(n log(n)). It's been proven that no comparison sort can operate faster than this. Only sorts that rely on a special property of ...


63

The book is indeed correct, and it provides a good argument. Note that timings are not a reliable indicator of algorithmic complexity. The timings might only consider a special data distribution, or the test cases might be too small: algorithmic complexity only describes how resource usage or runtime scales beyond some suitably large input size. The book ...


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 ...


55

You're basically correct about P and NP, but not about NP-hard and NP-complete. For starters, here are the super-concise definitions of the four complexity classes in question: P is the class of decision problems which can be solved in polynomial time by a deterministic Turing machine. NP is the class of decision problems which can be solved in polynomial ...


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"....


44

It is typically called "performance optimization", but I would not call it "refactoring", since this term typically refers to changes in code which don't change its visible behaviour. And a change in Big-O is definitely something which I would call a visible change. in doing so I will change the fundamental way the operation runs In this case, your ...


38

When calculating the Big-O complexity of an algorithm, the thing being shown is the factor that gives the largest contribution to the increase in execution time if the number of elements that you run the algorithm over increases. If you have an algorithm with a complexity of (n^2 + n)/2 and you double the number of elements, then the constant 2 does not ...


38

The complexity of merge sort is O(nlogn) and NOT O(logn). Merge sort is a divide and conquer algorithm. Think of it in terms of 3 steps - The divide step computes the midpoint of each of the sub-arrays. Each of this step just takes O(1) time. The conquer step recursively sorts two subarrays of n/2 (for even n) elements each. The merge step merges n ...


35

I know with O(n), you usually have a single loop; O(n^2) is a double loop; O(n^3) is a triple loop, etc. How about O (log n)? You're really going about it the wrong way here. You're trying to memorize which big-O expression goes with a given algorithmic structure, but you should really just count up the number of operations that the algorithm requires and ...


34

You've overlooked the key characteristic of the logarithm base. Because i is divided by 2 in each iteration, the running time is logarithmic with base 2. And log2(500) ~ 8.9 What you are looking at is log10(500) ~ 2.7 (logarithm with base 10) By the way, the reason why the base is often omitted in runtime discussions (and your calculator probably ...


31

The normal merge sort algorithm - merge step with normally apply n + m -1 comparisons, where one list is of size n and and the other list is of size m. Using this algorithm is the most simplest approach to combine two sorted lists. If the comparisons are too expensive you could do two things - either you minimize the number of comparisons or you minimize ...


27

Formally, big-O notation describes the degree of complexity. To calculate big-O notation: identify formula for algorithm complexity. Let's say, for example, two loops with another one nested inside, then another three loops not nested: 2N² + 3N remove everything except the highest term: 2N² remove all constants: N² In other words two loops with another ...


27

No, it cannot be. It looks like it can from this graph because it is a log-log plot, which means both the x and y axes are compressed. Any function which satisfies the relation y = a*x^c for some constants a and c will appear as a straight line in a log-log plot. So the simple answer is the "sub-linear" case is not a straight line. This is evident from the ...


26

The idea is that an algorithm is O(log n) if instead of scrolling through a structure 1 by 1, you divide the structure in half over and over again and do a constant number of operations for each split. Search algorithms where the answer space keeps getting split are O(log n). An example of this is binary search, where you keep splitting an ordered array in ...


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

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. ...


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 ...


20

The Big Oh notation (O, Theta, Omega) is about growth rates of functions. When you implement an algorithm, it has a certain characteristic how the runtime changes when you increase the dataset operates on. Now, you may optimize the algorithm so it runs faster by a factor of 100. Sure, this is great, but essentially, it's still the same algorithm. Similarly, ...


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 | · ·...


17

Because the index n of an array points to the n+1th element in the array (using zero-based indexing). Some simple math allows you to calculate the exact position of the desired element in O(1). Further Reading Java Arrays


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 ...


16

This is basically a math question, it might be better on "Computer Science" stackexchange or even SO. But I guess you can expect programmers to know it also, and Programmers is not only for "Soft" questions so maybe it is well placed here. Anyways. Based on the answers so far, I believe that Phillip Kendall has misread your question. He thinks you are ...


16

Your reasoning is incorrect. The rule that you can discard irrelevant terms only applies to additive terms, but in your case the parts are multiplied. If the logarithm in your case has base 2, 2^ld(n) is actually n, so the total complexity is n^3, which most definitely is not n^2.


14

The key to understanding why array access is O(1) is understanding that they have a known length. In a language like C, we can guarantee this by allocating a sequential block of memory. Since it's sequential in memory, we can use pointer arithmetic for direct addressing and thus direct access. An array object would follow a similar principle with its ...


14

It is very easy to eliminate your confusion because it comes from a single word: O(n) represents the upper bound of the function. That's incorrect. The correct statement is: O(n) represents an upper bound of the function. Big-O notation does not mean that the function named in the notation is the least upper bound, just that it is an upper bound. ...


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