So, I've been reading as usual, as I found something to-the-point and interesting which is worth sharing with you people.
Its about Big-O Notation. How one can simply explain what Big-O Notation is.. Here is the answer.
This is a true story.
In 2009, a South African company named The Unlimited grew frustrated by their ISP’s slow internet and made news by comically showing just how bad it is. They “raced” a carrier pigeon against their ISP. The pigeon had a USB stick affixed to its leg and was taught to fly to an office, 50 miles away. Meanwhile, the company transferred this same data over the internet to this same office. The pigeon won -- by a long shot.
What a joke this ISP was, right? A BIRD could transfer data faster than them. A bird!
Their internet may or may not have been slow, but this experiment doesn't say much. No matter how fast or slow your internet is, you can select an amount of data that will allow the internet or a pigeon to win.
Here's why:
How long does it take a pigeon to fly 50 miles with a 10 GB USB stick attached to its leg? Let's say it takes about 3 hours. Great.
Now, how long does it take to transfer 10 GB on the internet? Let's say you have pretty fast internet, and 10 GB only took 30 minutes. Okay, then transfer 100 GB and you know it will take more than 3 hours.
How long does it take that same pigeon to "transfer" 100 GB? Still 3 hours. The pigeon's transfer speed doesn't depend on the amount of data. (USB sticks are pretty light but can fit a ton of data.)
So, just like that: the pigeon beat the internet!
The pigeon's transfer time is constant. The internet's transfer time is proportional to the amount of data: twice the data will take about twice as much time.
In Big-O time, we'd say that the pigeon takes O(1) time. This means that the time it takes to transfer N gigabytes varies proportionally with 1. That is, it doesn't vary at all.
The internet's transfer speed is O(N). This means that the amount of time it takes varies proportionally with N.
Now, what if you had something that was O(N^2)? This would mean that the time varies with the size of N squared.
A real life example of an O(N^2) problem would be the time it takes to paint a square wall of length N (note: N is the length of the wall, not the area of the wall). If I make the edge of my square twice as long, the area of the square wall increases 4x.
Big-O offers an equation to describe how the time of a procedure changes relative to its input. It describes the trend. It does not define exactly how long it takes, as a procedure with a larger big-O time than another procedure could be faster on specific inputs.
Note: If you’ve taken an algorithms class, you might remember that, technically, big-O refers to an upper-bound. Anything that is O(N) could also be said to be O(N^2). To describe the exact runtime, we should be using big-theta.
However, outside of an algorithms class, this distinction has basically been forgotten about. People use big-O when they should really be using big-theta.
Its about Big-O Notation. How one can simply explain what Big-O Notation is.. Here is the answer.
This is a true story.
In 2009, a South African company named The Unlimited grew frustrated by their ISP’s slow internet and made news by comically showing just how bad it is. They “raced” a carrier pigeon against their ISP. The pigeon had a USB stick affixed to its leg and was taught to fly to an office, 50 miles away. Meanwhile, the company transferred this same data over the internet to this same office. The pigeon won -- by a long shot.
What a joke this ISP was, right? A BIRD could transfer data faster than them. A bird!
Their internet may or may not have been slow, but this experiment doesn't say much. No matter how fast or slow your internet is, you can select an amount of data that will allow the internet or a pigeon to win.
Here's why:
How long does it take a pigeon to fly 50 miles with a 10 GB USB stick attached to its leg? Let's say it takes about 3 hours. Great.
Now, how long does it take to transfer 10 GB on the internet? Let's say you have pretty fast internet, and 10 GB only took 30 minutes. Okay, then transfer 100 GB and you know it will take more than 3 hours.
How long does it take that same pigeon to "transfer" 100 GB? Still 3 hours. The pigeon's transfer speed doesn't depend on the amount of data. (USB sticks are pretty light but can fit a ton of data.)
So, just like that: the pigeon beat the internet!
The pigeon's transfer time is constant. The internet's transfer time is proportional to the amount of data: twice the data will take about twice as much time.
In Big-O time, we'd say that the pigeon takes O(1) time. This means that the time it takes to transfer N gigabytes varies proportionally with 1. That is, it doesn't vary at all.
The internet's transfer speed is O(N). This means that the amount of time it takes varies proportionally with N.
Now, what if you had something that was O(N^2)? This would mean that the time varies with the size of N squared.
A real life example of an O(N^2) problem would be the time it takes to paint a square wall of length N (note: N is the length of the wall, not the area of the wall). If I make the edge of my square twice as long, the area of the square wall increases 4x.
Big-O offers an equation to describe how the time of a procedure changes relative to its input. It describes the trend. It does not define exactly how long it takes, as a procedure with a larger big-O time than another procedure could be faster on specific inputs.
Note: If you’ve taken an algorithms class, you might remember that, technically, big-O refers to an upper-bound. Anything that is O(N) could also be said to be O(N^2). To describe the exact runtime, we should be using big-theta.
However, outside of an algorithms class, this distinction has basically been forgotten about. People use big-O when they should really be using big-theta.
0 comments:
Post a Comment