Since a graph of n vertices has n choose 2 pairs, the total number of DAGs of n vertices has an upper bound of 3^(n choose 2). This is much smaller than n^n.
It is much larger. =
, and
is much larger than n.
3^(10 choose 2) is about 10^21.
Since the nodes of these graphs are all distinguishable, there is no need to factor out by graph isomorphism, so 3^(n choose 2) is the exact number.
That's the number of all directed graphs, some of which certainly have cycles.
Surveyed. Looking forward to the data and analysis, as per every year.
It's one thing to create a weapon that can be used to kill O(100,000) people at once (though, it's not really "at once" if you do it by dropping N bombs consecutively). It's another thing to create a weapon that can only be used to kill O(100,000) people at once.
Or something. Of course, if inventing nukes is evidence humans aren't very moral, the fact that people chose to kill a hundred thousand people in Tokyo with conventional weapons is a different kind of evidence for humans being not very moral.
That's not how Big O notation works: O(100,000) = O(1).
You presumably mean "in the order of 100,000", which is sometimes written "~100,000".
</pedantry>
= f037147d6e6c911a85753b9abdedda8d){kind=logo}
= 27d567bc2d48d9f40e9ccc20ea370b15)
= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
I learned math with the Peano axioms and we considered the symbol
2to refer to the1+1, 3 to(1+1)+1and so on. However even if you consider it to be more complicated it still stays an analytic statement and isn't a synthetic one.If you define 2 differently what's the definition of 2?
In type theory and some fields of logic, 2 is usually defined as (λf.λx.f (f x)); essentially, the concept of doing something twice.