O(2^N) denotes an algorithm whose growth will double with each additional element in the input data set. The execution time of an O(2^N) function will quickly become very large.
abalfazl hossein wrote:http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
O(2^N) denotes an algorithm whose growth will double with each additional element in the input data set. The execution time of an O(2^N) function will quickly become very large.
I read this article. But unfortunately this article does not have any example for O(2^N). May you give me code example and describe more?
Thanks
SCJP 6. Learning more now.
Do you feel the same ?
No, it calculates the (n + 1)th member of the commonest fibonacci series.abalfazl hossein wrote: . . . This code calculate Fibonacci nth number. . . ..
abalfazl hossein wrote:
Do you feel the same ?
Yes, I don't know why a person who must be a developer or programmer must know many things about math, as Integral and so on..
abalfazl hossein wrote:But unfortunately has not example for O(n^2).
Stephan van Hulst wrote:I'm guessing he's still referring to O(c^n).
Assume T(n-1) = O(2n-1), therefore
T(n) = T(n-1) + T(n-2) + O(1) which is equal to
T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)
Alternatively, you can draw the recursion tree, which will have depth n and intuitively figure out that this function is asymptotically O(2^n).
Google for bubble sort. You can write a program to test it in about ten minutes.abalfazl hossein wrote:I want an example for this : O(2^n) . . .)
Finding the (exact) solution to the traveling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Campbell Ritchie wrote:
No, it calculates the (n + 1)th member of the commonest fibonacci series.abalfazl hossein wrote: . . . This code calculate Fibonacci nth number. . . ..
http://en.wikipedia.org/wiki/Bubble_sortBubble sort has worst-case and average complexity both О(n^2),