0

This is my homework(I have attempted it, and there are no references for questions like these)

Determine whether or not these functions are polynomial run time and determine the constant c for O(n^c) based on these functions:

3^(log base2 (n))

(log base2 (n))!

My intuition tells me yes for both.

Case 1: The exponential will always dominate, regardless of what number is put as n. since its log base 2, it will grow "exponentially" as n is increased.. however I do not know how to prove it

Case 2: Using n! as a reference, since n! is equivalent 2^n, then (log base2 (n))! must be equivalent to 2^(log base 2 (n))

Apprentice Programmer
  • 111
  • 1
  • 1
  • 5
  • 1
    Read some good math book. Actually your question is not much related to programming. – Basile Starynkevitch Jan 06 '15 at 06:35
  • possible duplicate of [What is O(...) and how do I calculate it?](http://programmers.stackexchange.com/questions/132331/what-is-o-and-how-do-i-calculate-it) – gnat Jan 06 '15 at 09:15
  • 1
    This question appears to be off-topic because it is about maths, not programming. It may be on-topic on [Math.StackExchange](http://math.stackexchange.com/), but it's highly likely to be a duplicate there. – Jörg W Mittag Jan 06 '15 at 11:24

2 Answers2

3

  1. Calculate log(3^(log_2(n)))

  2. n! is not equivalent to 2^n. See Stirling's approximation for the factorial.

kevin cline
  • 33,608
  • 3
  • 71
  • 142
1

Since this is clearly homework I am not going to throw the answers out there, but I will give you some tips for approaching them.

For your first problem, you need to think back to the definition of a logarithm. What would the answer be if it were this?

2^(log base2 (n))

If I plug four in for n, the log would evaluate to two. The power would then evaluate to four. If I plug 8 in, I get 8. In other words, any base b raised to the log base b of any value n gives n. The exponentiation and the log cancel each other out with the same base.

What happens if the exponentiation has a larger base than the logarithm? Smaller base? How fast do polynomials grow compared to exponentiation and logs regardless of base?

For the second problem, what happens when you apply any exponentiation or factorial to a function that is polynomial or lower? What dominates in the long run, assuming you are not doing 2^(log2(n)) or something else that cancels out?

Remember, with Big-Oh you need to think about arbitrarily large trends. Not specific numbers, just think if you looked down the n axis trillions of values out, what is the dominating factor? I could plot 1.00000000000000000000000001n and it will stay very small for a long time but eventually it will grow faster than n10000000000000000. Granted in practice the first is preferable to the second, but we are talking theory here, not production-quality algorithms.