# 342: 1337: Part 2

1337: Part 2 |

Title text: Trivia: Elaine is actually her middle name. |

## [edit] Explanation

Donald Knuth is a computer science Professor Emeritus at Stanford University who is famous for writing The Art of Computer Programming and developing the TeX computerized typesetting system. He may not have a mountain hideaway ^{[citation needed]} (a reference to *Kill Bill*, by the way), but he would be one of the best mentors a budding hacker could have.

The A* search algorithm and Dijkstra's algorithm are graph search algorithms. And what study of algorithms would be complete without a healthy study about finding complexities? Time complexity is the amount of time an algorithm takes to execute. Upper and lower bounds for complexity is written in Big O notation. Best possible execution of an algorithm is constant time, or O(1), said in words, for any given data set no matter how large the algorithm will always return the answer in the same time. However, constant time is extremely difficult to achieve; linear time (O(n)) is also very good. For more complex algorithms, O( n*log(n) ) is good, but O( n*log(log(n)) ) is better. (Note that logarithms in different bases are proportional to each other. So this would hold true for any base >1.)

From the evidence that Mrs. Roberts has two children, a daughter named Elaine, and a younger son named Bobby (presumably Bobby'); DROP TABLE students;--), we can assume that she is the same mother from 327: Exploits of a Mom. Of course, the title text here explains that Elaine is only her middle name. In 327 we learned her first name is "Help I'm trapped in a driver's license factory". Mrs. Roberts appears to have had fun naming her children.

All comics in "1337" series:

- 341: 1337: Part 1
- 342: 1337: Part 2 (this one)
- 343: 1337: Part 3
- 344: 1337: Part 4
- 345: 1337: Part 5

This series was released on 5 consecutive days (Monday-Friday) and not over the usual Monday/Wednesday/Friday schedule.

## [edit] Transcript

- [Cueball standing near a friend, who is on the floor near the armchair.]
- Friend: So the greatest hacker of our era is a cookie-baking mom?
- Cueball: Second-greatest.
- Friend: Oh?

- [A young Elaine with a ponytail is laying on the floor looking at the screen of a computer that appears to have been pieced together. A younger Bobby is finger painting at an easel.]
- Mrs. Roberts had two children. Her son, Bobby, was never much for computers, but her daughter Elaine took to them like a ring in the bell.

- [The back of a car is in frame. Mrs. Roberts is waving goodbye to her daughter who is wearing a backpack and is holding a walking stick. She is about to begin climbing a staircase built into a mountain.]
- When Elaine turned 11, her mother sent her to train under Donald Knuth in his mountain hideaway.

- [Donald Knuth is standing with a pointing stick at a chalk board with graph traversal patterns on it.]
- For four years she studied algorithms.
- Knuth: Child—

- [Knuth whips around slashing the stick like a sword. Elaine jumps and lands on the stick.]
- Knuth: Why is A* search wrong in this situation?
*swish*- Elaine: Memory usage!
- Knuth: What would you use?
- Elaine: Dijkstra's algorithm!

- [They are outside both working on a chalkboard with a separator down the middle so they cannot look at each other's work. Elaine is no longer wearing her hair in a ponytail.]
- Until one day she bested her master
- Knuth: So our lower bound here is O(n log n)
- Elaine: Nope. Got it in O(n log (log n))
- And left.

## [edit] Trivia

- In this Google-speech Donald Knuth personally asked Randall what his
*n*log(log(n))*algorithm for searching was, and Randall referred him to Elaine.

**add a comment!**⋅

**refresh comments!**

# Discussion

Well, imho the reference to the master in the mountain hideaway is clearly a reference to Kill Bill, but I am not skilled enough in English to write it myself... 217.162.253.103 13:06, 6 March 2013 (UTC)

- Next time, don't be so shy! Just do the best you can and someone else can help correct it. Alpha (talk) 00:21, 7 March 2013 (UTC)

I don't see why dijkstra's algorithm would use less memory than A*. Any ideas? 24.18.133.138 01:44, 13 July 2013 (UTC)