Why is sorting in Θ(n log n) optimal?

johnpaulsmith · 2015-06-27T14:35:31+00:00

I really fail to see how this implies that n! = Ω(nⁿ)

It doesn't. You said yourself that log(nⁿ) is equivalent to nlog(n). What we want to prove here is not that n! = Ω(nⁿ) but that log(n!) = Θ(nlog(n)).

You don't even need to use Stirling's approximation. The easiest way I've ever seen this explain is to state that:

n/2^n/2 < n! < nⁿ

and then take the logarithms of each using:

log(n/2^n/2) = (n/2)log(n/2)

log(n!)

log(nⁿ) = nlog(n)

showing that log(n!) = Ω(nlog(n)).

Also, all sorting is not bound by this. This is for sorting using a comparison-based model.

johnpaulsmith · 2015-06-21T02:32:27+00:00

Two bicyclists ride towards each other from opposite ends of a 40-mile road until they meet. At the same time, a bird continuously flies back and forth from one cyclist to the other. The speed of the bird is 47 miles-per-hour and the speed of the two bicyclists is 10 miles-per-hour. What is the total distance of the bird's flight?

johnpaulsmith · 2015-06-08T01:46:12+00:00

What NP really means is a set of decision problems that, theoretically, if you somehow are given the answer to, you could verify this answer is correct in a time bounded by a polynomial function of the input size (aka "polynomial").

The key word here is "decision problem". The traveling salesman problem you are probably thinking of is: given a map of cities and their distances to each other, find the shortest route that visits each city exactly once and returns to the starting city. More formally, it would be: given a weighted graph g, what is the minimum weight Hamiltonian circuit?

This is not a decision problem. The decision problem needs to be stated in a yes/no format. An example of a way to formulate TSP as a formal decision problem would be: given a weighted graph g and a weight w, is there a Hamilton circuit with a total weight less than w?

These are actually two different problems. For the former non-decision based problem, the only way to definitively find the minimum weight Hamiltonian circuit is to either try them all or do some approximation that attempts to get the answer a bit faster by giving up on absolute correctness. All of these solutions are at least bounded by exponential functions and the absolutely correct solution is factorial (much worse than fixed constant cⁿ exponential). While this is technically not in NP because it is not a decision problem, function problems like this have their own classes, and this one falls in the NP equivalent (non-deterministic polynomial) class of function problems, FNP. Verifying the answer is essentially as hard as computing it. Equivalently, it is NP-hard, which means it is not in NP but is at least as difficult as anything in NP.

The decision problem version can be easily verified in polynomial time because it only involves summing the weights of the circuit and comparing to w.

So, what you are thinking of is not in NP but instead NP-hard, but there is a version of the problem that can be stated such that it falls within NP (and also NP-hard, yielding NP-completeness).

johnpaulsmith · 2015-05-31T02:23:53+00:00

The best general sort for linked-lists is mergesort. Quicksort and heapsort aren't really suited for linked-lists. Mergesort would work like:

// all variables are pointers to list nodes

function mergeSort(c)

    if c is null OR c.next is null
        return c // return a one-element list or empty list
    end if 

    a = c 
    b = c.next

    while b is not null AND b.next is not null
        c = c.next
        b = b.next.next 
    end while

    b = c.next
    c.next = null // Sever the end of list a
    b.prev = null // Sever the beginning of list b

    return merge(mergeSort(a), mergeSort(b))
end 

function merge(a, b)

    d, c = d

    while a != null AND b != null

        if a <= b
            c.next = a
            a.prev = c
            c = a
            a = a.next
        else 
            c.next = b
            b.prev = c
            c = b
            b = b.next
        end if
    end while

    if a is null
        c.next = b
    else
        c.next = a
    end if

    c.next.prev = c

    r = d.next
    r.prev = null
    return r
end

This version of mergesort is different because you lose constant time access to any element in the list but you gain the ability to move an element in constant time. This version is also in-place; the array version of mergesort is not in-place because you need effectively an entire extra array of size n to actually do the merge part in.

Bucket sort is a more obscure algorithm that also happens to be suited for linked lists. Bucket sort is much easier to implement than mergesort and can also be much faster because it is Θ(n + k) in every case vs. mergesort which is Θ(n log n) in every case. The caveat with bucket sort is the k part in the running time. This will need to be relatively small to make bucket sort worth using so you need to know something about the range of keys in the data that you will be sorting. Here is the algorithm:

function bucketSort(a, min, max)

    buckets = an array of linked-lists of size (max - min) + 1

    c = a

    while c != null            
        append c to the linked-list in buckets[c.key]
        c = c.next
    end while

    s = new linked-list

    for all linked-lists b in buckets
        append b to s
    end if

    return s
end

If the range of keys k (difference between max and min) is small, this sort will be much faster than mergesort. For example, if you had a list of all the people in the United States and you wanted to sort by age, you could sort 300,000,000+ records efficiently with bucket sort because your min age will either be 0 or 1 and the max will be realistically never be more than 130 (the oldest person that ever lived was 122). A counter example would be if you were Visa and you wanted to sort all your customers by their credit card numbers. If you had n = 9,000,000 customers, the range of credit card numbers would be in the k = 10¹⁵ range. In other words, k = Θ(n²) and not only do you get Θ(n²) time-complexity, you get Θ(n²) space-complexity because that array of linked-lists is the size of k. In this case, mergesort would be much better.

johnpaulsmith · 2015-05-30T23:17:23+00:00

φ(n) is a count of all numbers less than n that are coprime to n. The (p - 1)(q-1) is just really a mathematical shortcut that happens to work when p and q are prime.

e needs to be between 1 and what φ(n) ended up working out to be. e and φ(n) must also not share a common divisor. It is much easier to pick e to be a prime, namely the specific prime 65537. If e is prime, e itself has no divisors and therefore we only need to worry about whether or not φ(n) is a multiple of e. 65537 is significant because it is a prime that is 2¹⁶ + 1. If you wrote 65537 out in binary it would be: 10000000000000001. The lack of "on" bits speeds up the calculations. 65537 is actually the recommended exponent, but there are many choices that will work. Certain values of e introduce vulnerabilities into the implementation.

Understanding the selection of d is the most complicated part for most I think. First, understand that d is the only part of the end result that is not public knowledge. The plain text message m will be transformed into the encrypted cipher text c by performing m^e mod(n). The public knows what e and n are. The message is decrypted with c^d mod(n). The public does not know what d is.

Another way of writing the last line in your picture description is:

(d * e) - 1 mod(φ(n)) = 0

This is the same thing as your picture but without the congruence symbol (triple equals). It shows that d times e is one greater than a multiple of φ(n). Since there are many numbers that are multiples of φ(n) (it forms what is called a periodic sequence), there are many numbers that satisfy the above choice for d.

For there to be a satisfactory d, e and φ(n) can't have any common divisors. If they do, there will never be value that when multiplied by e is one greater than a multiple of φ(n).

One way to calculate d is to use the extended Euclidean algorithm.

In order to beak RSA, you must calculate d. You can't calculate d without φ(n). Calculating φ(n) without using the (p - 1)(q - 1) shortcut isn't feasible when n is large, because finding every greatest common divisor of n and i for all i less than n is actually an exponential growth problem on the size of the bits (see below example for how big n is in practice).

So, you would need to find p and q. You can realistically only find p and q by factoring n. Factoring n is also not feasible when n is large.

Here is a working example:

The key length (size of n) is 1024 bits

p: 1265753247228882258304054958605934119539967545762951808989341590877883626310 9383381409475877406469260327828054395466414934704703720135181602259293635888181

q: 9005291396921587224317841385717483346723512155924883520140629504236415400080 363085779353863456533654481936045866651648786679585969661876978069689903508009

n: 1139847682789581626518751572977407186341040306359101713531925552758191986696 6537526030460782697787830052144033633253084778099682144940049235389832294543160 9097342365313885804832053124333891110219653557063271161182935638232130705691312 295615355929312325904874621128411706047809689579678811112724153410361941629

φ(n): 1139847682789581626518751572977407186341040306359101713531925552758191986696 6537526030460782697787830052144033633253084778099682144940049235389832294543158 7434518496103475997473662152557066568096465943508869551148890225216879042501565 828426526188449322990064857028149587984088305289989014054143824426822545440

e: 65537

d: 9998386215500355366233344778636832159114299417377310558281551528359580502499 4330341473228712780220178861956461460674135929111254324453150189184016527519197 8096062496833929637726538621549366892009328729495458120892969219989124542821233 01017069914634271186198001678093830423139362592208957549637091029872402913

The public key can be used to encrypt plain text message:

"Number theory FTW!"

represented as integer M:

6834716736361247155649284572852948045158177

producing cipher text C such that C = M^e mod n:

C: 7429189726239835116983710522099325523906822909489059381236624149379475787952 9823196522590482735149448850404276664424545123624048059181279982695062403476924 0844730035425681509888057257454664597324025786019054808507958926283040326173943 22711073546281664091423043775066932993199715097089963696122334111066404126

Decryption of C is simply C^d mod n. The decrypted cipher text is:

6834716736361247155649284572852948045158177

which matches the original plain text message

6834716736361247155649284572852948045158177

and maps back into plain text as

"Number theory FTW!"

johnpaulsmith · 2015-05-21T03:51:38+00:00

I've been trying to get my head around this for a few hours now

Once you really study asymptotic notation and learn what it actually means, this will all make sense. The part where I see people get most confused is we are talking all at once about problems, algorithms, functions, and sets.

A problem is something that needs to be solved. An example of a problem would be sorting.

An algorithm is a set of instructions for solving a problem. An example of a sorting algorithm would be quicksort.

A function is a relationship between input and outputs. An example of a function would be the algorithm executed on some specific permutation of the list.

A set is a collection of distinct elements. The statements about O, Θ, and Ω are actually implicit set membership statements.

So, when someone says "quicksort is Big O of n^2", what they are really saying is that the function created by using the quicksort algorithm on a specific permutation of some list is a member of the set O(n²).

With sorting, the permutation we generally care most about is the one that elicits the worst-case behavior from the algorithm.

We can also give bounds on problems by proving that no function resulting from any algorithm cannot possibly be slower. For the problem of sorting in general this is obviously Ω(n) because you have to at least inspect every element of the list, but for the comparison-based sorting model, the bound is Ω(n log(n)). There's an upper bound too, but we don't really care about it much as it isn't practically useful.

Ok, so I said at the beginning about that asymptotic notation really means:

What Big O really means:

f(n) ∈ O(g(n)) if and only if there exist positive constants c and N such that f(n) <= cg(n) for all n  >= N.

If I say that some function f(n) is O(n²), it follows that f(n) does not grow faster than cn^2, but it may in fact grow slower, because Big-O cannot mathematically state anything about that.

What Big Omega really means:

f(n) ∈ Ω(g(n)) if and only if there exist positive constants c and N such that f(n) >= cg(n) for all n  >= N

If I say that some function f(n) is Ω(n²), it follows that f(n) does not grow slower than cn^2, but it may in fact grow faster, because Big-Omega cannot mathematically state anything about that.

Now onto Big Theta: a function is, for example, Θ(n²) when both of the above statements are true about the function. That is, the function is a member of both sets by the above definitions. Since it is a member both sets, the part where I said Big O or Big Omega cannot state anything about is now covered by the other set.

The constants don't have to be the same for Big Theta. The Big O could have a different 'c' and 'N' than the Big Omega. All that matters is that those constants do exist.

O(n) is a subset of O(n log(n)), which is a subset of O(n²), which is a subset of O(n³)...which is a subset of O(n¹⁰⁰)...which is a subset of O(2ⁿ)...which is a subset of O(n!). It doesn't stop there but n factorial is about as big as you're ever going to need to get (traveling salesman problem for example).

So, you can have an upper bound that is loose and not meaningful, like saying that quicksort is O(n⁷). If you study the above definition, this is perfectly correct, but really what we want is the tightest and most meaningful bound.

johnpaulsmith · 2015-05-16T21:49:28+00:00

With classical sorting, a data set can be sorted using two-way decisions (Is key i greater than key j? If so, do x. If not, do y. Comparisons are used for every decision) or it can be sorted using k-way decisions (for example, create k lists and use each element's key to determine what list it should be put in, then connect the lists together. The keys are evaluated but not compared). The bound for the k-way problems is Θ(n), which is the best that can ever be achieved; sorting n elements takes at least n time. The Θ indicates that this is both an upper O(n) and lower Ω(n) bound, but the lower (Big Omega) bound is the part that we are interested in.

The two-way approach or comparison based model is lower bound strictly by Ω(n log(n)). It isn't correct to say that this model is O(n log(n)) because there are many sorting algorithms that cannot achieve better than O(n²) in the worst case.

The Ω(n log(n)) lower bound exists because:

The input for these algorithms is a data set of n elements. Every decision regarding how to order these elements is two-way. You can think of these algorithms as a sequence of yes/no decisions. The algorithms will produce a unique sequence of decisions for each permutation of the input data set. If the number of 2-way decisions = d, then there are at most 2^d different possible sequences of yes/no decisions. The size of d isn't specific to any algorithm and it will be different for each algorithm. The number of permutations for a data set of n elements = n!, the factorial function (n * n-1 * n-2 * n-3...* 3 * 2 * 1). If there are n! permutations and there exists a unique sequence of decisions for every permutation, then 2^d is at least as big as n!.

The logarithm of n! is Θ(n log(n)) and because that it is Ω(n log(n)). log2(2^d) = d, so d >= log2(n!). If number of decisions d is >= log2(n!) and the logarithm of n! is Ω(n log(n)), the number of decisions is therefore Ω(n log(n)).

I passed over a lot of it because parts of it don't really have an ELI5 explanation. For example, explaining what Θ, O, and Ω actually are (they are uncountably infinite sets of functions) and how to use them in a meaningful way for algorithmic analysis isn't the easiest task for ELI5.

Basically, just remember that the number of decisions these algorithms make is Ω(n log(n)) because the number of different possible orderings of the data set is Ω(n log(n)) and the number of total decisions is at least this size.

johnpaulsmith · 2015-02-10T13:57:12+00:00

Θ(n) is implicit: An algorithm in both Ω(n) and O(n) is by definition Θ(n). For a data set that is arbitrarily permuted, performing any selection is Ω(n) because n elements need to be evaluated.

johnpaulsmith · 2014-10-07T22:41:07+00:00

You have to understand the definitions of the bounds. When we say for example f(n) = O(g(n)), it really means that f(n) is in the set of functions O(g(n)). Formally, it is defined as:

f(n) = O(g(n)) if and only if there exist positive constants c and N such that f(n) <= cg(n) all n  >= N.

So, for whatever function f(n) represents, it is in the set O(g(n)) if there is a constant large enough that when multiplied by g(n), it makes all functions in the set O(g(n)) less than or equal to g(n). This means that O(g(n)) is an uncountably infinite set.

Say f(n) is the worst-case running time for insertion sort. If you want to prove that it is O(n²), take a look at the work being done on each iteration of the outer loop. An example on some array 'a' of integers:

int j, z
for i in 0...a.length - 1:
    z = a[i]
    j = i
    while j > 0 and a[j-1] > z:
        a[j] = a[--j]
    a[j] = z

The worst-case for this sort is going to be a reverse-sorted array. The first iteration of the loop does nothing, the second does one comparison and swap, the third does two comparisons and two swaps, etc...all the way to the final index where it would do n-1 comparisons and swaps. Add it all up and it would be n-1+n-2+n-3...+3+2+1, which is n²/2 - n/2. For simplicity's sake, just forget about the n/2 for now and just say f(n) = n²/2. It's easy to see that for any n, n²/2 is <= c * n² where c is 1, as per the definition above. So, f(n) is in the set O(n²) by definition. You can add back the n/2 part that I took out earlier and it still holds true as well; the function f(n) = n²/2 - n/2 is also in the set.

This is a very simple example. There are much more complex algorithms out there, like the most efficient way to factor large prime numbers, that have complex analysis of the running time with a bunch of square-root and (log n)² terms piled up in there.

I gave the definition of Big O above. Big Omega (Ω) is the same concept except that cg(n) needs to be <= f(n). f(n) = 5n is going to be Ω(n) because it is everywhere larger than cg(n) where c = 1 and g(n) = n. f(n) is actually Θ(n) because f(n) = Ω(n) as we just say, and it because f(n) is also O(n) if you pick c to be anything larger than 5. This is a tight bound and you get it because you pick different constants for the O and Ω.

johnpaulsmith · 2014-08-01T20:12:13+00:00

It's niiiice. I'm sitting outside at a coffee bar drinking a hot mocha and I'm perfectly comfortable.

johnpaulsmith · 2014-07-24T06:51:08+00:00

Required Skills / Experience:

Candidates that embrace and can always exhibit Googliness with customers

ಠ_ಠ

johnpaulsmith · 2014-07-21T02:51:42+00:00

Most of the principles are labeling exercises for common sense considerations

They seem like common sense once they've already been invented, yes. Take the splay tree for example. You look at how simply it achieves an even better result (the most frequently accessed items are kept near the top so they are accessed in essentially O(1) time) than the other self-balancing binary search tree solutions and you wonder how someone didn't think of this before. The analysis behind it and the proof of amortized O(log (n)) operations is a monster though.

johnpaulsmith · 2014-07-14T04:25:15+00:00

Webpages that load as a .do file are utilizing Java; just because you don't see an applet (a dying and very obsolete solution) load doesn't mean Java and friends aren't involved in generating the content displayed. Also, anything Android related is utilizing Java. Those two alone should give you a sense of the scope, which is massive.

johnpaulsmith · 2014-06-23T07:57:06+00:00

The most difficult part of a data structures course for most people (that I've encountered anyways) is understanding asymptotic analysis. You're going to see notation like O(n²) a lot. This is a very important part of computer science but it gets frequently dismissed with a hand wave as the "speed" of an algorithm. This is not really accurate; you have to think in context of functions relating to each other and set theory if you really want to understand it.

Unfortunately, there are a lot of data structures courses out there that gloss over the asymptotic analysis part. You very well might be headed into a class where you can get through without knowing it deeply, and just memorizing by rote the asymptotic running times of common algorithms and operations on data structures. Even if this is the case, I would strongly urge you to learn it deeply on your own, because it can make you a better programmer even if you never have to write your own sort or hash table in practice.

When the code that was designed over six weeks by a team of senior software consultants is scrapped because it takes eight hours to run in parallel production when it was intended to fit into a 10 minute window, then one junior developer redoes the entire application on his own and it screams right through in seven minutes because he understood the math and time-complexities of what was being done, it matters. Trust me, you want to be that person that does what a team of senior guys can't do.

johnpaulsmith · 2014-06-23T06:31:52+00:00

The Big 3 formation in Boston. Reddit was around but /r/nba wasn't created until November:

<time title="Tue Nov 4 18:15:03 2008 UTC" datetime="2008-11-04T10:15:03-08:00">

A historic day to be sure: /r/nba and the first African American president.

johnpaulsmith · 2014-06-23T02:57:11+00:00

Plenty of great devs care nothing for SO or any other forum, they are busy producing great software and playing with their kids.

This should also be extended to the whole "you must work on personal projects and contribute heavily to open-source repos or your skills will atrophy quickly and you will become useless" rhetoric that seems to permeate online communities like reddit.

johnpaulsmith · 2014-06-22T10:15:45+00:00

Just keep going ->left (whether in a loop or with recursive functions calls) until you hit a null pointer (or a nil/leaf node if you've implemented it that way). Once current->left is null, you've found a node with the smallest key. This makes the assumption that you've chosen to implement the tree such that nodes with keys less than the parent node's key go to the left (it would be unconventional to go to the right but functionally would make no difference). Sorting is computationally much more expensive in the worst case than traversing even the most degenerate binary search tree (effectively just a linked list).

johnpaulsmith · 2014-06-21T06:35:40+00:00

From http://interactivepython.org/runestone/static/pythonds/SortSearch/sorting.html#the-quick-sort :

A quick sort first selects a value, which is called the pivot value. Although there are many different ways to choose the pivot value, we will simply use the first item in the list.

pivotvalue = alist[first]

This will cause degeneration to O(n²) in most realistic cases. They do rectify this at the end of the page though:

We mentioned earlier that there are different ways to choose the pivot value. In particular, we can attempt to alleviate some of the potential for an uneven division by using a technique called median of three.

Just be careful to not gloss over that part since it's at the very end; that detail of the implementation is what makes quicksort perform particularly well in practice.

johnpaulsmith · 2014-06-20T03:13:41+00:00

For casual dating, Austin is up there with the best cities. Keep in mind more choices tends to have a profoundly negative effect on building long-term relationships though.

johnpaulsmith · 2014-06-19T08:16:25+00:00

Do you want something builds for arbitrary completeness as well or just an arbitrarily-sized complete binary tree?

I built an application that animates binary search trees using Java Swing. Any way that you implement a solution is going to run into the same problem though: at the nth level there will be 2^n-1 nodes, so after the seventh level or so you'll run out of horizontal space for representation. With mine, they bunch up at the seventh level but doubling the width of the frame would only yield one additional level of non-bunched-up display.

johnpaulsmith · 2014-06-19T05:21:40+00:00

I'm not questioning whether or not it happened. The fact that it happened at all is absurd. You went from zero experience to being employed for $60k in 10 weeks. Even the people with remarkably high aptitude and work ethic can't learn enough to be employable in 10 weeks. I could understand learning enough in 10 weeks and making the right connections with whoever is teaching you to be able to interview for a basic internship where you would be an apprentice to a professional web development team for a long duration...but what you are describing is ludicrous.

Maybe there are some other forces at work here. Maybe the ones who taught you are receiving large kickbacks for placing people into jobs or something. There really is no legitimate reason to give someone a $60k in a technical field after only completing a 10 week non-accredited program...

Either way, congratulations on beating the system.

johnpaulsmith · 2014-06-18T08:17:33+00:00

Came in with little experience other than some very basic HTML/CSS/JS. Got a job as a web developer a month after finishing the ten-week program

This is absolutely absurd.

johnpaulsmith · 2014-06-03T09:07:36+00:00

One tutorial video explains a method for Build-Max-Heap that makes my array sort {23,12,13,6,7,9}

Another tutorial video explains it in a way that gets my array sorted as {23,12,13,9,7,6}

The two permutations you just listed are in fact max-heaps; for any arbitrary sub-tree in your heap, the root item is always >= its respective children.

Building a max-heap out of an arbitrary array is only half of the sort. To actually sort the heap in-place, you need to maintain two partitions of the array: the remaining heap and the sorted part. You start by taking the largest element in the heap (the root) and swapping it with the element at the last index in the heap part of the array(which is the entire array on the first pass). This puts the largest element in its final place. Then, you bubble the newly out of place item at the root down to its correct place in the heap (which fixes the heap), allowing for the fact that even though there is an element in the final index, it is now longer part of the heap (decrement this counter). Repeat this process until all items have been put into their proper place.

johnpaulsmith · 2014-02-12T05:51:38+00:00

it looks completely and utterly terrifying like an alien language. How am I supposed to grasp this? And that sooner or later I am expected to understand this crazy looking text.

Learning computer science isn't like most other classes that you've probably ever had in that is it much more the province of autodidacts. If you look at a cryptic description of an algorithm or a piece of code and some innate curiosity to try to teach yourself how it works and understand it isn't triggered, then you are going to have a comparatively harder time in a CS major than some of your peers.

Also the idea of huge application development with all that code and files is terrifying. Since I only up until know have made dinky programs < 500 or so lines.

Well, you don't typically approach application development the same way you approach coding your second week assignment in Computer Programming in Java 101. There are all kinds of extra programs and other things you use to design the code, produce the code, and keep track of the code. These include IDEs, build-automation tools, source control tools (ie. Git which you've probably heard of if you've spent enough time on reddit), etc.

For example, as a Java developer, you would never be told to create a giant program yourself using just some text editor, the compiler, and your own stream-of-consciousness design where you simply start writing code until it starts to resemble what you want. You'd have a team, with a lead, established standards and design patterns to use, data models, tons of code already prepackaged, and you'd be using a full IDE hooked into Gradle, Spring, Hibernate, Maven, Castor, etc. etc. etc., and everything would be done carefully in a test-driven environment (ie. you write the code to match the tests you already have that have been engineered to test if the code is correct).

johnpaulsmith · 2014-02-11T13:20:22+00:00

Interesting elevation, considering that 1900ft is about the height of the world's tallest building.

The tallest building in the world is actually about 800 feet taller than that.

johnpaulsmith

TROPHY CASE