Hacker Newsnew | comments | show | ask | jobs | submit | devinj's comments login

No, it means the worst case is bounded above and below by n^2. That is, the worst-case scales no worse or better than n^2, but approximately proportional, asymptotically. (Whereas, for example, every O(n^2) algorithm also happens to be O(2^n))

The best case is something entirely separate, and can itself be bounded from above or below.

-----


It doesn't make sense to say there's an upper and lower bound on the "worst" case. If that were true, the upper bound would be the new worst case, and the lower bound would be some middle case. A best or worst case is inherently always going to be big-theta.

-----


This talks about our ability to reach or describe the worst case, so if we say it's Ɵ(n^2), we're saying that we can tell that the worst case is at least quadratic, and it's also no worse than quadratic. We might not be so good at the math and have only discovered that the worst case was at least linear and no worse than exponential (which is true of quicksort).

-----


Can you MITM public wifi? Real question, but I thought the answer was "no", which would make public wifi a compelling counter-example.

-----


Yes. You arp poison the default gateway and route traffic through your own host instead.

-----


Or spoof DNS responses to point to a machine under your control.

-----


Or spoof a disassociation frame, then impersonate the access point so the victim connects to your computer instead.

-----


I have no idea where you'd get the idea that the answer is "no". The answer is emphatically yes.

-----


I don't actually think that's more significant than self-driving cars -- getting things faster is one thing, changing the way we travel is another. Imagine a world where nobody dies in traffic accidents anymore? No drunk driving nonsense, etc. -- that's a far different and better world than one where the only new thing is "hey hey I can use my phone to get stuff in ten minutes".

-----


> Imagine a world where nobody dies in traffic accidents anymore? > "hey hey I can use my phone to get stuff in ten minutes".

If I get the replacement parts for my vacuum cleaner for tomorrow, I won't get in a car or any transportation mechanism to get it to some store. As a side effect, your traffic accident number is down (less individual people driving) and the system efficiency is also up (efficient vehicles moving the goods).[]

What amazon does goes toward the goal you state. It does it in a small way, but it's here today, you can use it now, and it should continue doing it better and better everyday.

Google's self driving car might reach your goal to some point in some distant future. If infrastructure gets a lot better. And legislation problem get solve. And Google is still around by then. Is it so much better ?

[] BTW, You'll still have drunk people, but this problem might as well be solved by other means than self-driving cars.

-----


Addressing the challenges of population, energy, food, other resource availability, and negative environmental impacts comes to mind.

Self-driving cars could be a part of that. But small in the bigger picture.

-----


http://www.spur.org/publications/article/2012-12-18/corporat...

"The City of Mountain View [...]expressly rejects housing as an allowable use in the area."

IIRC there was another rejection late last year, but I can't find it.

-----


> I can hardly imagine a way to satisfy the protesters' demands for cheaper rent without taking away that landlord's fundamental right to charge what he wants for use of his own property.

There's two ways to do it, and that's neither of them: increase supply (build new structures; apparently SF has over-restrictive policies on building that could be loosened?) or decrease demand (e.g. make corporate-run buses illegal).

-----


> decrease demand (e.g. make corporate-run buses illegal).

AFAIK, those buses aren't operated by the companies themselves, but by external transportation companies as contractors. What would you make illegal, "don't take Google as a customer"?

-----


No, not at all. Requiring an increase of 2048 bits over 14 years implies that computing power increases by a factor of 216 every year.

-----


That would be true if RSA keys were brute forced, but they aren't - e.g. 512 bit RSA takes days/weeks to break on commodity hardware these days, whereas 512 bit brute force (as is essentially needed for ECC these days) takes significantly longer than the estimated age of the universe.

See http://en.wikipedia.org/wiki/Integer_factorization_records

-----


You need to factor in speedups due to advances in factoring algorithms, too. And it's possible that the software doesn't have any options between 2048 and 4096. (I have no idea, I didn't check.)

-----


It's pretty feasible, you just don't want to give it up.

-----


That's the typical response. Except that reality doesn't concur. People who stop using Facebook end up excluded from social circles. Not through malice, but because it's harder to be in contact with that one offhand person who Doesn't Even Own A TV--er, sorry, Doesn't Use Facebook. They're sand in the social gears.

(The self-centered prick's response of "then they're not real friends"--which I am addressing because it frequently comes next--willfully ignores that said self-centered prick is making it harder on everyone else to include them. They get excluded because they're being annoying. You have to give to get, and part of your giving is not making everyone else's life difficult because you're frothy about a web company.)

In the U.S. at least, if you have a basic appreciation of people you have formed friendships with over the years, if you value interacting with them over that self-centered Facebook froth, it's not feasible to ditch it. But you can still express a desire for it to improve.

-----


I usually get irritated at unnecessary references to a person's size, but I think the closer made it all worth it.

-----


Well, there's also the consent decree. I don't think anyone wants one of those...

-----


St Croix here.

-----

More

Applications are open for YC Winter 2016

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: