Basic structure of a divide-and-conquer algorithm:

Do ﻿﻿ preliminary work to prepare for doing recursive solutions.
Split the problem into ﻿﻿ sub-problems, each of size ﻿﻿ (with ﻿﻿), and recursively solve each of them.
Do ﻿﻿ wrap-up work to combine recursive solutions into a final solution.

Another example, a couple different analyses:

Stooge Sort

Problem: Given (an array of) \$n\$ things, sort them in ascending order.

Algorithm:
1: If the first thing is greater than the last thing, swap them.
2: If there are less than three things to sort, you're done.
3: Stooge sort the first 2/3 of the things.
4: Stooge sort the last 2/3 of the things.
5: Stooge sort the first 2/3 of the things.

Correctness:
If there are 0 or 1 elements to sort, line 1 does nothing, and line 2 correctly terminates.
If there are 2 elements to sort, line 1 does all necessary sorting, and line 2 correctly terminates.
If there are more things to sort, then...
- line 1 never makes anything worse,
- line 2 won't cause early termination,
- line 3 will ensure that anything initially located in the first 1/3 which should be in the last 1/3 ends up in the second 1/3
- line 4 will ensure that anything currently located in the second 1/3 which should be in the last 1/3 ends up in the last 1/3 (i.e. everything that needs to be in the last 1/3 gets there), in the right order
- line 4 also ensures that anything currently located in the last 1/3 which should be in the first 1/3 ends up in the second 1/3
- line 4 also ensures that anything currently located in the last 1/3 which should be in the second 1/3 ends up in the second 1/3
- line 5 will ensure that anything currently located in the second 1/3 which should be in the first 1/3 ends up in the first 1/3 (i.e. everything that needs to be in the first 1/3 gets there), in the right order
- line 5 also ensures that anything currently located in the first 1/3 which should be in the second 1/3 ends up in the second 1/3, in the right order
- line 5 also ensures that anything currently located in the second 1/3 which should be in the second 1/3 ends up in the second 1/3, in the right order

So, as a result of the recursive steps, everything ends up in the 1/3 it should be in, and each of those 1/3rds are in the correct order, which is to say that the whole thing is in the correct order.

Termination:
Each recursive call makes, at most, a comparison, a swap, a size check, and three recursive calls on strictly smaller subsets. Since there are only finitely many strictly smaller subsets, and each step branches to at most three substeps, by things such as Kőnig's lemma (or just "finite times finite is finite") there will be at most finitely many steps each of which do finitely much work, so this stops.

Analysis, take one:
If ﻿﻿ denotes the running time of a stooge sort handling ﻿﻿ elements, we have the recurrence relation
﻿﻿﻿
Here, ﻿﻿ is a constant indicating how many constant-sized steps are taken at each stage, and ﻿﻿ is a (possibly 0) constant taking into account that splitting the problem into 3 subproblems might require a linear scan through the list (with an array, it doesn't, but this ends up not hurting the final result).

We unroll this a few times...
﻿
﻿and simplify
﻿
﻿and unroll
﻿
﻿and simplify
﻿
and do it until a pattern is apparent ...
﻿
and remember that for big-O notation, "rounding up" is ok. So replace ﻿﻿ with the larger ﻿﻿, and replace ﻿﻿ with the ever so slightly larger ﻿﻿
﻿
So, we're at the point where, as long as ﻿﻿ satisfies ﻿﻿, we can plug in any ﻿﻿ we like and

﻿﻿
will be true. And, of course, if ﻿﻿ is such that ﻿﻿, we're at the bottom-out case where ﻿﻿

| As is standard in an unrolling argument, the thing to do is find out when ﻿﻿ (and note, ﻿﻿ so this is a bottom-out case)...
|
| To solve
| ﻿
﻿| divide by the coefficient of n
| ﻿
﻿| take logs of both sides (I'll leave the choice of which base to later, and just call it x)
| ﻿
﻿| divide by the coefficient of k
| ﻿
﻿| and whatever you chose x to be, that expression just means
| ﻿

If we use that particular value for ﻿﻿, then we see
﻿﻿
﻿﻿
No need to drag around extra constants, let's let ﻿﻿:
﻿﻿
While this is a bound on the running time (and a good bound, to boot), it's lacking something in the readability department. So, a few more transformations courtesy of "rules of logarithms" and "multiply by one":

Starting from here
﻿﻿
We can find that ﻿﻿ and ﻿﻿ where ﻿﻿ (again, note, the particular base doesn't matter for a ratio of logs)
| First, since ﻿﻿, we have
﻿| ﻿
﻿| ﻿
| Also, since ﻿﻿, we have
﻿| ﻿
﻿| ﻿
﻿| ﻿
| Now, by rules of exponents, ﻿﻿, so
﻿| ﻿
| And since for any ﻿﻿ we like, ﻿﻿
﻿| ﻿

| Similarly, since ﻿﻿, we have
﻿| ﻿
﻿| ﻿
| By rules of exponents, ﻿﻿, so
﻿| ﻿
| And since for any ﻿﻿ we like, ﻿﻿
﻿| ﻿

So, since ﻿ and ﻿ we can plug those into ﻿ to get
﻿﻿ where ﻿﻿

Which is to say, the running time for Stooge Sort is ﻿﻿. If you're curious, that's only slightly better than ﻿﻿, making this worse than mergesort, worse than quicksort, worse than heapsort, worse than bubblesort, worse than insertion sort, worse than selection sort, and generally worse than any reasonable sorting algorithm! It is, nonetheless, a rather elegant algorithm, having just one real operation (swap first and last if out of order) and handling everything else by a clever overlapping recursion.

Analysis, take two:

Rather than unrolling, if we had some reason to think the time on this was polynomial (perhaps it is close enough to ﻿﻿ subproblems of size ﻿﻿ each?), we could try to find the exponent...

Given the recurrence relation ﻿﻿, what happens if we assume that ﻿﻿ for some unknown value of ﻿﻿? Note that the constant and linear parts don't interfere with ﻿﻿ being ﻿﻿, as long as ﻿﻿, but they may help cancel things out, so they're worth including.

Plugging the assumption into the recurrence relation, we want to find ﻿﻿ such that
﻿﻿
Having those constant and linear placeholders comes in handy here, because if ﻿﻿ and ﻿﻿, then our equation becomes
﻿﻿
If they hadn't been included from the start, we could have gone back and added them, keeping in mind that we can add ANY amount of work to an allegedly ﻿﻿ algorithm, as long as it's no bigger than ﻿﻿. Constant is fine. Logrithmic is fine. Linear is fine. Even ﻿﻿, which is smaller than any polynomial with ﻿﻿, is fine to throw in. Even if only to make things cancel nicely.

That equation has ﻿﻿ buried on both sides, so divide out by that...
﻿﻿
And shift the fraction to the left
﻿﻿
Time to take logs (whatever base) of both sides
﻿﻿
And solve for ﻿﻿
﻿﻿

Conclusion: Stooge Sort does take polynomial time ﻿﻿ where, in particular, ﻿﻿.