0

Consider the function F: 2^(3*n) + n^2

Can the function A: 2^(3*n) be used as a Big Theta, Omega or O as a characterisation of F? Why?

I'm revising the concepts of Big Omega, Big Theta and Big O and I came across this example but don't know where to start.

Sorin Cioban
  • 2,237
  • 6
  • 30
  • 36
  • do you want to know the complexity to calculate F, or is F a function for the complexity of some other algorithm? – Shep May 06 '12 at 16:51

2 Answers2

1

No.

2^(3*n) is the leading term, but unless you're doing something very wrong it's not going to take you that long to compute. Wikipedia has a good list of time complexities of various functions. The most complicated operation you're doing is raising to a power, the complexity of which is discussed in other posts.

Since you're looking at a function of the form g(f(x)) where g(x) = 2^x and f(x) = 3x, the time to compute is going to be O(h) + O(k), where h is the time complexity of g, k is the time complexity of f. Think about it: it should never be more than this, if it were you could just break the operation in two and save time by doing the parts separately. Because h is going to dominate this sum you'll typically leave the k term off.

Community
  • 1
  • 1
Shep
  • 7,990
  • 8
  • 49
  • 71
0

Yes, all three. In general, you only need to pay attention to the fastest growing term, as slower growing terms will be "swamped" by faster growing terms.

In detail:

Obviously F grows faster than A, so F \in \Omega(A) is a no-brainer. There is a positive multiple of A (namely A itself) that is smaller than F, for all sufficiently large n.

Try plotting F against 2*A. You will find that 2*A quickly gets bigger than F and stays bigger. Thus there is a positive multiple of A (namely 2*A) that is bigger than F for sufficiently large arguments. So by the definition of O, F \in O(A).

Finally, since F \in \Omega(A) and F \in O(A), F \in \Theta(A).

Theodore Norvell
  • 15,366
  • 6
  • 31
  • 45
  • we seem to be interpreting this question in two different ways... I was looking at the complexity of F, you're looking at F as a complexity. Funny that we posted opposite answers, though. – Shep May 06 '12 at 14:18
  • No, I'm considering the complexity of F. I think what you are considering is the complexity of computing F. Which is, as you point out, a whole other matter. – Theodore Norvell May 06 '12 at 14:28
  • Isn't "the complexity of a function" just a short way of saying "the complexity of computing a function"? – Shep May 06 '12 at 14:48
  • Thanks to both of you for the answers, but now I'm uncertain which one is more appropriate for my question. – Sorin Cioban May 06 '12 at 16:46
  • @SorinCioban, it really depends on what you want to know: this answer is assuming you're dealing with an algorithm that has complexity F, whereas my answer assumes the algorithm _is_ F, and you want to know the complexity _of_ F. – Shep May 06 '12 at 16:53
  • Oh ok. My question is inclined towards your answer then (i.e, the algorithm is F and the complexity would be A. So in this case, the complexity is 2^n+3n, right? – Sorin Cioban May 06 '12 at 17:03
  • @Shep asks 'Isn't "the complexity of a function" just a short way of saying "the complexity of computing a function"?' Ok. I really should not have written "the complexity of F". A complexity class is a set of functions. It is fair to say that F is in this complexity class or that it is not in that complexity class. The OP asked about whether certain classes "characterize" a given function. I interpret "characterizes" as "contains". – Theodore Norvell May 06 '12 at 21:35
  • I don't know what @SorinCioban wants, actually. If F is a _complexity_ function, then your answer is perfect. If F is a function and we want to know its complexity, my answer is the correct one. Can we agree on that? – Shep May 06 '12 at 21:47
  • Change "its complexity" to "the complexity of calculating it" and I'm in 100% agreement. – Theodore Norvell May 08 '12 at 16:10
  • And if @SorinCioban really wants to know the complexity of calculating F, the next question is, in what model of computation? If you assume binary representation, large enough registers, and that shifting, multiplying, and adding are all \Theta(1) time, then calculating F is \Theta(1) time. If the size of the registers is fixed, then I'm fairly certain that the time complexity is the \Theta(n). – Theodore Norvell May 08 '12 at 16:32