What in an exact formal manner does the expression

```
f(n) = 2^O(n)
```

mean?

The correct way would be to have 2^{n} as the bounding function.

O(2^{n})

f(x) = O(g(x)) as x→infinity if and only if there exist two numbers M and y such that for all x > y, |f(x)| ≤ M |g(x)|.

So, applying this to your expression, there exists two numbers M, y such that for all n > y, |f(n)| ≤ 2^{M |n|}. The right hand side of that is just equal to 2^{M}·2^{|n|}, **so the original expression is actually equivalent to f(n) = O(2 ^{n})**.

For more information, check the formal definition on Wikipedia.

The statement `f(n) = 2^O(n)`

is equivalent to

```
log_2(f(n)) = O(n)
```

(actually, any logarithm will do), so it means that there is some constant `C > 0`

such that

```
log_2(f(n)) <= C*n <=> f(n) <= 2^(C*n)
```

for all large enough `n`

. Now, a^{b*c} = (a^{b})^{c}, so another way to put it is to say

```
f(n) = O(b^n)
```

for some `b > 0`

. This `b`

could be `1.5`

, or `4`

, or `1000000000000`

, so it doesn't tell you too much. All it gives you is that `f`

is exponential, so it's asymptotically better than `O(n!)`

, but it doesn't tell you whether it's pretty bad, bad, really bad or truly catastrophically bad.

Similar Questions

I am having a hard time understanding Dijkstra's big O notation exactly. I have a question regarding Dijkstra with an unsorted array. As from Wikipedia: The simplest implementation of the Dijkstra's

Ok, I am trying to understand the concept of Big O. I have a function I am suppose to find the Big O and I am not quite getting it this is an example in the book of one that is like my homework.. I

I want to calculate the result, given any exponent (negative or positive) and a base of type integer. I am using recursion: public static double hoch(double basis, int exponent) { if (exponent > 0)

for(int i=N; i>0; i=i/2) irrelevant statement; I am asked to find the complexity class and I am unsure of whether I am supposed to use Big-Omega notation or Big-O? But I am assuming that it is O(N

I would like calculate the Hurst exponent with R. Is there a library or built in function that can do this? any suggestion will be appreciated (even weblinks to references). thanx update: thanx to the

I am trying to figure out how to determine Big O notation for recursive methods . I realise that is probably the same way as with a iterative method, but im not sure about this. I wrote this simple r

Prove, using only the definition of O(), that 2^sqrt(x) is not O(x^10). I have been doing a few exercises on Big O and this is the first time I have encountered the variable in the exponent. I was won

I have been given some code to work out big O runtimes on them, could someone tell me if I am on the right track or not? //program1 int i, count = 0, n = 20000; for(i = 0; i < n * n; i++) { count++

I am trying to find the Big O for stooge sort. From Wikipedia algorithm stoogesort(array L, i = 0, j = length(L)-1) if L[j] < L[i] then L[i] ↔ L[j] if j - i > 1 then t = (j - i + 1)/3 stoogesort

I know that the relation n = Big-O(1) is false. But if we use induction involving Big-O it can be proved. But the fallacy is we cannot induct Big-O. But my question is how we can disprove the relation

So I recently encountered a question which asked to order different functions in growth order where g1=O(g2), etc and to partition the list into equivalence classes iff f(n)=(theta O)(gn). In the answ

I often here people talk about Big O which measures algorithms against each other Does this measure clock cycles or space requirements. If people want to contrast algorithms based on memory usage what

I am trying to understand how this O notation works and I have below here a block of code, and next to each LINE I will have a comment with the time complexity that I believe it to be. If I am wrong p

I've been having some problems trying to grasp the concept of big O notation. So, by definition big O is as follows, T(n) ∈ O(G(n)) if T(n) <= G(n) * C. Since the the constant C can be any integ

For some reason im unable to solve this. what will be the Big-o Notation for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { c[i][j] = 0; for (int k = 0; k < n; k++) c[i][j] += a[i][k]

I'm trying to brush up on my big o calculations. If I have function that shifts all of the items to the right of 'i' 2 spaces I have a formula that looks something like: (n -1) + (n - 2) + (n - 3) ..

Hello I am having trouble finding the running time for this algorithm with following assumptions that s = O(logN) and the running time of Random_Integer is constant time: 1 express N-1 as 2^t * u whe

If I have a loop construction like this for(int i=1; i<n;i++) for(int j=1; j<n;j++); O(n2) or O(0)? Assume that inside the loop is an if: for(int i=1; i<n;i++) for(int j=1; j<n;j++) if(a=

The question asks me to determine the big-O notation for the following efficiencies: 1) 3n3/2 + 3 n1/2 + 10logn + 105n +5 2) 5 n3 +10n2logn 3) 105logn+10n3logn+10n2 4) 3n2+5n3/2 +151logn Here are my

So I have a quick question on how to verify the big O of a function. for example: a quicksort algorithm sorting an array of 5000000 element yields a time interval of 0.008524 seconds, running the same

Suppose an algorithm is known to be O(N2) and solving a problem of size M takes 5 minutes. About how long will it take to solve a problem of size 4M? Is it as simple as ... M=5min 4M=20min ?

Is O(2^(n^c)) = O(n^c*(2^(n^c))), where c is some constant? The context for this is showing that NP is a subset of DTIME(2^n^c) for all c > 1.

I'm having trouble converting a exponent number like 9.471347923322231e+18 into an nsnumber. Does anyone know how to do it the other way around? Thanks.

I'm learning programming using YouTube and whatever I can find. I stumbled upon some Big O problems and I'm quite confused on one of them. for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++)

What all algorithms do you people find having amazing (tough, strange) complexity analysis in terms of both - Resulting O notation and uniqueness in way they are analyzed?

I've read the topic: Big O, how do you calculate/approximate it? And am not sure what the Big-O notation for the following function would be: static int build_nspaces_pattern(const char * const value,

Give the smallest O() estimate you can for the following functions: 4n2 + 5n – 8 = O(...) log(n)2 + n = O(...) If you guys can, explain the answer rather than giving it to me. A question like this wi

What is the best/worst/average case complexity (in Big-O notation) of a trie data structure for insertion and search? I think it is O(K) for all cases, where K is the length of an arbitrary string whi

We just started learning big-o in class. I understand the general concept that f(x) is big-o of g(x) if there exists two constants c,k such that for all x>k |f(x)|<=c|g(x)|. I had a question whe

Please let me know the Big Oh of the above.

Possible Duplicate: are there any O(1/n) algorithms? Is it ever possible for your code to be Big O less than O(1)?

Below method getValue parses a String, builds a Map based on the String and returns a value associated with the key. Is performance of method below getValue O(n) squared ? I'm basing this on becau

I am having problems analyzing this method for its Big O complexity. In fact, I am also unsure of how the method works due to its confusing nature. For now, all I figure out is that the a gradually s

Maybe I'm mistaken in my understanding of Big-O notation (it has been a while since I've taken a course on algorithms) but the following has never made too much sense to me: This would be considered O

I'm struggling with understanding Big O and I'm unable to quite comprehend the multiple ways that I read, and watch, that are used to find the Big O of a function. It seems that every video or post ha

Possible Duplicate: Plain English explanation of Big O I was recently asked about my knowledge of how to use Big O notation and I was stumped because I had never come across Big O before. I have rea

I want to calculate Big O of x++ in below algorithm. for (int i = 2;i < n;i*=2) for(int j = i;j < m;j*=j) x++; I think a lot about it, but I can't solve it. How can I solve it?

For RSA, how do i calculate the secret exponent? Given p and q the two primes, and phi=(p-1)(q-1), and the public exponent (0x10001), how do i get the secret exponent 'd' ? I've read that i have to do

What would be the big O notation of the length of the list of permutations of the characters of a list of words of lenght n? I just do not know how to express that because it would be like n! for each

I'm looking to increment the exponent of a float (without touching the mantissa) in Java. I understand how to retrieve the exponent with Math.getExponent() and increment it, but am unsure about how to

I am playing around in PHP with RSA and big numbers. I need to be able to take numbers to the power of an exponent that has ~256 to ~512 bytes using gmp_pow(). Does anyone have any suggestions?

Using an ADT Linked List and the following code, how would I express the runtime in Big O Notation?: def reverse (self): (1)if self._head is not None: (2)temp = self._head.item (3)self._head = self._h

Im studying for a test and a practice problem states: True or False: O(n^3 + n^2) dominates O(n^4) Do we count O(n^3 + n^2) as O(n^5)? If so it does dominate.

Need some help on solving this runtime recurrence, using Big-Oh: T(n) = T(n/2) + T(n/2 - 1) + n/2 + 2 I don't quite get how to use the Master Theorem here

I'm attempting to guess and prove the Big O for: f(n) = n^3 - 7n^2 + nlg(n) + 10 I guess that big O is n^3 as it is the term with the largest order of growth However, I'm having trouble proving it. My

I have two separate pieces of code for which I need to calculate the Big O complexity. The first one is: k:=1; s := 4; while k < N do begin k := 2 * k; m:=1; while m < N do begin for i := m to

Can some help me with a function which is Big O(1) but not Ω(1) and the other way around? Some explanation would greatly help.

The great people at MyCodeSchool.com have this introductory video on YouTube, covering the basics of Big-O, Theta, and Omega notation. The following definition of Big-O notation is provided: O(g(n) )

We did an exercise in class today dealing with big-O notation. Here is one of the problems: void modifyArray(int a[], int size) { int max = a[0]; for (int i = 1; i < size / 2; ++i) { if (max < a

I'm asked to give a big-O estimates for some pieces of code but I'm having a little bit of trouble int sum = 0; for (int i = 0; i < n; i = i + 2) { for (int j = 0; j < 10; j + +) sum = sum + i +