Computational Complexity

What the Simulator Does

Our preflop odds come from a Monte Carlo simulation. For each starting hand, the simulator deals a random opponent hand and a random five-card board from a freshly shuffled deck, finds each player's best five-card hand, and records a win, a tie or a loss. It repeats that 1,000,000 times for every starting hand in the game.

Three numbers decide how much work that takes: how many starting hands there are, how many trials each one gets, and how many five-card hands have to be evaluated in each trial.

Counting the Starting Hands

A starting hand of k cards from a 52-card deck can be dealt in C(52, k) = 52! / (k! (52 − k)!) ways. Each extra hole card multiplies the count:

For a fixed k, C(52, k) grows like 52^k / k!: going from two hole cards to four multiplies the hands by about 204, and the fifth card multiplies them by 9.6 more. See Combinatorics for how these counts are built.

Hand Evaluations per Trial

In Hold'Em a player's best hand is any five of their seven cards, so each player has C(7, 5) = 21 hands to compare. In Omaha a player must use exactly two hole cards and three board cards, which gives C(4, 2) × C(5, 3) = 6 × 10 = 60 hands each. Five-card Omaha has C(5, 2) × C(5, 3) = 100. With two players in every trial:

Each evaluation is a single table lookup: before the run, every one of the 2,598,960 possible five-card hands is ranked once and stored, so scoring a hand afterwards takes constant time, O(1).

Total Work in Big O

The total number of hand evaluations is W = H × T × E where H is the number of starting hands, T the trials per hand and E the evaluations per trial. For an Omaha-style game with k hole cards, E = 2 × C(k, 2) × C(5, 3), which grows like k², so W = O(C(52, k) × T × k²)

The work is linear in the number of trials and in the number of starting hands; the combinatorial growth lives entirely in H. Omaha takes about 580 times the work of Hold'Em, and five-card Omaha 16 times the work of Omaha.

So do all poker games have the same complexity? Big O notation can carry more than one variable, and here there are two that matter: T, the trials per hand, and H = C(52, k), the starting hands for k hole cards. The evaluations per trial, E, stay small (from 42 to 400), soW = O(H × T)Within a game, H is fixed and the work is O(T): every game is linear in its trials. Between games, the deck stays at 52 cards and what changes is k. Each extra hole card multiplies the starting hands by (52 − k) / (k + 1): 25.5 times going from one card to two, 16.7 from two to three, 12.25 from three to four and 9.6 from four to five.

Worked out with the real deck, as starting hands times evaluations per trial:Hold'Em: C(52, 2) × 42 = 1,326 × 42 = 55,692Omaha: C(52, 4) × 120 = 270,725 × 120 ≈ 3.2 × 10⁷Omaha 5: C(52, 5) × 200 = 2,598,960 × 200 ≈ 5.2 × 10⁸Big O: C(52, 5) × 400 = 2 × (Omaha 5) ≈ 1.0 × 10⁹Big O has the same starting hands as Omaha 5; playing Hi-Lo only doubles E. In Big O notation that factor of 2 is a constant and drops out, so both are O(C(52, 5) × T). The constant still matters in practice: it is the difference between about 30 and 59 days below.

Big O Notation

Big O describes how work grows with the size of a problem, ignoring constant factors. Formally, f(n) = O(g(n)) means there are constants c and n₀ such that f(n) ≤ c × g(n) for every n ≥ n₀ Big Theta, f(n) = Θ(g(n)), adds the matching lower bound: f grows exactly as fast as g, up to constants.

The growth rates that show up in poker odds:

On a full deck the gaps are enormous. At n = 52, O(n) is 52 steps and O(n²) is 2,704. C(52, 4) is 270,725, the number of Omaha starting hands, and 2⁵² is about 4.5 × 10¹⁵. On a log scale a polynomial bends over while an exponential runs in a straight line: every card added doubles it.

In poker the deck is always 52 cards, so the input that grows from game to game is the number of hole cards k. Through five cards, C(52, k) grows almost exponentially in k: each extra card multiplies the starting hands by roughly ten to twenty-five.

Runtime Scenarios

Measured on new hardware (an Apple M4 Pro, twelve worker processes, a vectorized engine), one pass of 100,000 trials takes about 0.7 minutes for all of Hold'Em and about 4.4 hours for all of Omaha. Ten passes give the 1,000,000 trials behind our numbers:

Big O, the poker game, is Omaha 5 played Hi-Lo: the pot is split between the best high hand and the best qualifying low. It has the same 2,598,960 starting hands as Omaha 5, but every player's best low has to be found as well as their best high, so each trial takes 400 evaluations instead of 200, and the run takes twice as long.

The Omaha run works through about 2.0 × 10⁸ hand evaluations per second. The Omaha 5 and Big O rows are projections at that rate, which is why the next games move to a GPU. Our first Omaha run, in 2019, used 20,000 trials per hand and took 43 hours on twelve processes, about 4.2 × 10⁶ evaluations per second: the new hardware and engine do roughly 50 times the work per second, enough to give every hand 50 times as many trials in about the same time.

Why Simulate Instead of Counting Every Deal

Exact odds would mean dealing every possible opponent hand and board. For one Hold'Em starting hand that is C(50, 2) × C(48, 5) = 1,225 × 1,712,304 ≈ 2.1 × 10⁹ deals, and for one Omaha starting hand C(48, 4) × C(44, 5) ≈ 2.1 × 10¹¹ Across all 270,725 Omaha hands, with 120 evaluations per deal, that is about 6.9 × 10¹⁸ evaluations: at 2.0 × 10⁸ per second, more than a thousand years. A million random deals per hand gets within a twentieth of a percent of the exact answer for a tiny fraction of the work.

How Many Trials Are Enough

Each trial is a random draw, so the measured equity carries sampling error. For an equity p measured over n trials, the standard error is SE = √(p (1 − p) / n) It is largest at p = 0.5:

Error falls as O(1/√n): ten times the accuracy takes a hundred times the trials. Going from 20,000 to 1,000,000 trials cut the error by a factor of √50 ≈ 7.1, which is what lets neighboring hands in our rankings be told apart.

Cutting the Work

Many starting hands differ only by suit. A♠K♠ and A♥K♥ have the same equity, so only one hand per suit pattern has to be simulated:

Suit symmetry cuts H without changing the Big O, because the classes still grow like C(52, k) divided by a constant. The other lever is the constant itself: every trial is independent, so the work splits across processors with almost no overhead, and a GPU runs thousands of evaluations at once.

Computational Complexity FAQ

What is the time complexity of a poker Monte Carlo simulation?

For a game with k hole cards, the total work is O(C(52, k) × T × E): the number of starting hands times the trials per hand times the hand evaluations per trial. With a lookup table, each evaluation takes constant time.

How many starting hands are there in Omaha?

There are C(52, 4) = 270,725 four-card Omaha starting hands, 16,432 of them distinct once suits are treated as interchangeable. Hold'Em has 1,326 (169 distinct) and five-card Omaha 2,598,960 (134,459 distinct).

Why does Omaha take so much longer to simulate than Hold'Em?

Omaha has 204 times as many starting hands and needs 120 hand evaluations per trial instead of 42, about 580 times the work in all.

What does O(1/√n) mean for simulation accuracy?

The sampling error shrinks with the square root of the number of trials: four times the trials halves the error, and a hundred times the trials cuts it tenfold.

Do all poker games have the same computational complexity?

In the number of trials, yes: within any one game the work is O(T). Between games, what changes is the number of hole cards k, and the starting hands C(52, k) multiply with each extra card, so Omaha takes about 583 times the work of Hold'Em and Big O about 18,700 times. Hi-Lo games double the evaluations, a constant factor that Big O notation drops.

How long would five-card Omaha take to simulate?

About 5.2 × 10¹⁴ hand evaluations at 1,000,000 trials per hand: roughly 30 days on the CPU that runs our Omaha simulation in about 44 hours.