Big-O Analysis--Complexity of algorithm
Hi All,
I was going through complexity of algorithm and they stated that
if n=10^5 and complexity f(n)=2^n then it takes 10^285 centuries for a processer to process that algorithm given that it can do million trasactions per second.
This is very shocking for me.Lets say I have 10^5 elements in my dynamic array and I have written program on that array that follows this 0(2^n) algorithm then would it take my computer 10^285 centuties to process it?
It looks very unreal for me.
Please help if my understanding is wrong.
Thanks
Prasad
I was going through complexity of algorithm and they stated that
if n=10^5 and complexity f(n)=2^n then it takes 10^285 centuries for a processer to process that algorithm given that it can do million trasactions per second.
This is very shocking for me.Lets say I have 10^5 elements in my dynamic array and I have written program on that array that follows this 0(2^n) algorithm then would it take my computer 10^285 centuties to process it?
It looks very unreal for me.
Please help if my understanding is wrong.
Thanks
Prasad
Yes. Keep in mind though, a complexity of O(2n) is fairly inefficient, so normally you should be able to find an algorithm that does the same thing in much less time, like a complexity of O(n2) or O(n log n). Things like this ridiculousness is actually how things like RSA work: The fastest algorithms (for traditional computers) to work out two prime numbers that multiply together for a different number are all worse than polynomial time (like your example there, which is in exponential time). For example, RSA768 (a key 768 bits long) took 2000 years of CPU computing time to crack.
Considering your example with 105 = 100,000 elements.
If you have an O(2n) algorithm (not that this is an oh not a zero, but that's a typographical point), that means you will be doing about 2100,000 transactions to compute the algorithm on that array.
2100,000 is a number that is over 30,000 digits long; divide that by 1,000,000 to see how many seconds it would take to complete those transactions, and you still have a number with over 30,000 digits.
There are about 32,000,000 seconds in a year, so divide by that to get the number of years you'll need. Divide by 100 for centuries and you (surprise) still have a result with more than 30,000 digits. However you look at it, that's a lot of centuries.
If you have an O(2n) algorithm (not that this is an oh not a zero, but that's a typographical point), that means you will be doing about 2100,000 transactions to compute the algorithm on that array.
2100,000 is a number that is over 30,000 digits long; divide that by 1,000,000 to see how many seconds it would take to complete those transactions, and you still have a number with over 30,000 digits.
There are about 32,000,000 seconds in a year, so divide by that to get the number of years you'll need. Divide by 100 for centuries and you (surprise) still have a result with more than 30,000 digits. However you look at it, that's a lot of centuries.
@NT3 @Zhuge
Actually few months back I started learninng programming and this complexity of algorithms looked silly to me especialy in times when memory and speed is not a concern.
However Now I do realise how improtant efficiency of algorithm is.
Thanks again for replies.
Actually few months back I started learninng programming and this complexity of algorithms looked silly to me especialy in times when memory and speed is not a concern.
However Now I do realise how improtant efficiency of algorithm is.
Thanks again for replies.
Topic archived. No new replies allowed.