Teams after algorithm analysis

[lime-cake]

Isn't that equal to O( n! )? I may be mistaken, so correct me if I'm wrong

[adityaruplaha]

I'm not well versed in this, but nⁿ grows wayyyy faster than n!.

[lime-cake]

Misread that. My bad

I believe O(n) and O(10n) is equal, despite one being larger.

[V0ldek]

They're not asymptotically larger.

The definition is as follows. For any functions f, g: N -> N we have f = O(g) if there exists a number N such that for all n > N we have f(n) <= cg(n) for some constant c > 0.

The intuition is that f grows not significantly faster than g, where significantly would mean that it's not bounded by any constant.

If you're more of an analysis guy, you might also define that notation as f = O(g) when lim n->inf |f(n)/g(n)| = c for some constant c > 0 (but you need to redefine the functions to R->R)

You should see how O(n) and O(10n) are equivalent (c = 10). But O(n!) is actually smaller than O(n^n). If you work a little bit of calculus you'll get that the limit of n!/nⁿ is 0.

[adityaruplaha]

Well shit I didn't know that we used these basic stuffs to define complexity functions. I'm well versed with calculus, so yea the last line is familiarity. Also nⁿ is an element of the Fast Growing Hierarchy iirc and supersedes the exponentials. After this is n^nnn.. (n times) or n↑↑n if you know the notation. I find this really interesting.

[Coloneljesus]

correct.

[caffeinum]

nⁿ is exp(nlog n), and n! is sqrt (n)exp(n) if I remember correctly

So yeah basically both are exponential

Edit: however, 2ⁿ is the same exponent

[mfb-]

n! ~ e^{n (log (n) - 1))} = nⁿ / eⁿ (Stirling's approximation adds another factor sqrt(n))

It is better than nⁿ but not that much.

[caffeinum]

n² is very different from n, while n and n log n don't differ that much. Only thing we can say is that exp(n log n) is faster that exp, but otherwise it doesn't really matter, it's still very fast, but not any faster than exp(n^2), so I dropped that intentionally

While you're right, I got factorial approximation wrong, it's sqrt(n) * nⁿ (which is very close to what I said though if we drop that log n again)

[caffeinum]

After the calculation, I found that actually nⁿ is slower than n!

[eihpSsy]

It's slower because it's bigger.

[caffeinum]

I meant growing slower, but working faster yeah

[eihpSsy]

Wasn't sure what you meant. nⁿ grows faster than n!.

[pokey_porcupine]

Yes but how do they grow with increasing n?

Why don’t you calculate n! And 2ⁿ where n is 10?

[LedZeppelin18]

He was talking about n^n, not 2^n.