How is the size of a bitcoin transaction calculated From what I understand, the fees set on bitcoin transaction are based on a recommended fee (mostly, from a 3rd party service) per byte of the transaction size. What I am curious about is how do wallets arrive at the size of a transaction?
Since the activation of Segwit, transaction size is expressed in Weight Units (WU). Weight Units can be converted to a "virtual size" or virtual bytes (vB) by dividing by 4 and rounding up. The virtual size dictates how large your transaction is when paying fees.

Non-Segwit Transactions

For now, let's focus on Non-Segwit transactions. Each Non-Segwit byte of data is counted is 4 WU when determining size. Each transaction consists of the following fields:


Version (4 bytes)
# of Inputs (VarInt, 1 byte for numbers up to 252)
Inputs (varies)
# of Outputs (VarInt, 1 byte for numbers up to 252)
Outputs (varies)
Locktime (4 bytes)


Let's break each of these fields down by looking at a non-segwit raw transaction:

0200000001d2eed35b0d55763981c635cab7788c28e3683af3d329947a17d7f6005390e6ef010000006a47304402200ffaac8f12e56f4af66109220812b76c7d6bb0e5906cf2de235b79496b3e080b0220037304894b648fa0b50e0d82ef9f58b537233ee282ab31fc04fb3d169d2c97cc0121030120a287eb98922752a89b39df64f7f3314036f6f096341c9189b0cb3c692aaeffffffff02404ff200000000001976a9140b818b11f9624e6a2d5b757a3e8fe45db3f6647788ace0b4b401000000001976a914a1e5e47fce1c5c0868107dba3851eb696c2ead5388ac00000000


Version

The version of this transaction is 02000000 (2 in little-endian). The version is always 4 bytes (16 WU).

# Of Inputs

The number of inputs is 01 (1 in VarInt notation). This indicates there is 1 input being spent by this transaction. This adds 1 byte (4 WU).

Inputs

All Inputs consist of the following fields:


Referenced Transaction Hash (32 bytes)
Output Index (4 bytes)
Script Length (VarInt, 1 byte for numbers up to 252)
ScriptSig (varies)
Sequence (4 bytes)


For our example transaction, the values are:


RefTX: d2eed35b0d55763981c635cab7788c28e3683af3d329947a17d7f6005390e6ef
Output Index: 01000000 (1 in little-endian)
Script Length: 6a (106 in VarInt notation)
ScriptSig: 47304402200ffaac8f12e56f4af66109220812b76c7d6bb0e5906cf2de235b79496b3e080b0220037304894b648fa0b50e0d82ef9f58b537233ee282ab31fc04fb3d169d2c97cc0121030120a287eb98922752a89b39df64f7f3314036f6f096341c9189b0cb3c692aae
Sequence: ffffffff


In total, this input adds 147 bytes (588 WU).

# Of Outputs

The number of outputs is 02 (2 in VarInt notation). This indicates there is 2 outputs being created in this transaction. This adds 1 byte (4 WU).

Outputs

All Outputs consist of the following fields:


Value (8 bytes)
Script Length (VarInt, 1 byte for numbers up to 252)
ScriptPubKey (varies)


For our example transaction, we have 2 outputs. The first output is:


Value: 404ff20000000000 (15,880,000 satoshi, in little-endian)
Script Length: 19 (25 in VarInt notation)
ScriptPubKey: 76a9140b818b11f9624e6a2d5b757a3e8fe45db3f6647788ac


In total, this output adds 34 bytes (136 WU).

The second output is:


Value: e0b4b40100000000 (28,620,000 satoshi, in little-endian)
Script Length: 19 (25 in VarInt notation)
ScriptPubKey: 76a914a1e5e47fce1c5c0868107dba3851eb696c2ead5388ac


In total, this output adds 34 bytes (136 WU).

Locktime

For our example transaction, the locktime is 00000000 (0 in little-endian). Locktime is always 4 bytes (16 WU).

In total, this transaction is 900 WU. Converting to vB gives us 225 vB. With an Input Value of 0.4491 BTC and a combined Output Value of 0.445 BTC, the total miner fee is 0.0041 or 410,000 satoshi. Converting this to sat/vB gives us a feerate of 1,822 sat/vB. (incredibly high!)

Segwit Transactions

A Segwit Transaction is any transaction which spends a Segwit input (aka an address beginning with "3" or "bc1"). Segwit Transactions include a few extra pieces of information like Witness data. Segwit Data is counted as 1 WU/byte and is therefore cheaper to include in transactions. This is why Segwit saves on fees. A Segwit Transaction consists of the following fields, with fields counting as Segwit Data being bolded:


Version (4 bytes)
Marker (1 byte)
Flag (1 byte)
# of Inputs (VarInt, 1 byte for numbers up to 252)
Inputs (varies)
# of Outputs (VarInt, 1 byte for numbers up to 252)
Outputs (varies)
Witness Data (varies)
Locktime (4 bytes)


Again, let's break each section down in an example Segwit Transaction:

02000000000101caba4ccb61cca412fe29ec553d286134a02335c04355a9cc1e056fe2403692cf1400000000fdffffff026406010000000000160014093c864a10516154d18d2accd61c6b2920a2040f60361e000000000017a9140195e8dd3d1527038a0a77e0b0e4515d6c8ab195870247304402200760efedbcee3bbd913661fb40c364caed622b331ee3b5bc70ac25df2d3763d5022020efdb41ef325089d146eb48948b6aaec85c086fa38a3df4d2a51ee729645ebc012102be338e0362fb01101a873a7502012cb82f7d9d303b4943fa0702829a763e49762b550900


Version

The version is, like before, 02000000 (2 in little-endian) and is always 4 bytes (16 WU).

Marker

The marker is 00 (0 in VarInt notation). The Marker indicates that this Transaction is a Segwit Transaction. Nodes running Segwit will see this marker and know to parse the transaction appropriately, and nodes not running Segwit will treat the marker as the "# of Inputs" field, discarding it as invalid for having 0 inputs. This adds 1 byte (1 WU).

Flag

The flag is 01 (1 in VarInt notation). The Flag indicates that Witness Data will be present in the transaction, and adds 1 byte (1 WU).

# Of Inputs

The number of inputs is 01 (1 in VarInt notation) indicating this transaction has 1 input. This adds 1 byte (4 WU).

Inputs

The first (and only) input is as follows:


RefTX: caba4ccb61cca412fe29ec553d286134a02335c04355a9cc1e056fe2403692cf
Output Index: 14000000 (14 in little-endian)
Script Length: 00 (0 in VarInt notation)
ScriptSig: [EMPTY]
Sequence: fdffffff


This input adds 41 bytes (164 WU).

# Of Outputs

The number of Outputs is 02 (2 in VarInt notation) indicating there are 2 outputs created in this transaction. This adds 1 byte (4 WU).

Outputs

The first output is as follows:


Value: 6406010000000000 (67,172 satoshi, in little-endian)
Script Length: 16 (22 in VarInt notation)
ScriptPubKey: 0014093c864a10516154d18d2accd61c6b2920a2040f


This output adds 31 bytes (124 WU). The second output is as follows:


Value: 60361e0000000000 (1,980,000 satoshi, in little-endian)
Script Length: 17 (23 in VarInt notation)
ScriptPubKey: a9140195e8dd3d1527038a0a77e0b0e4515d6c8ab19587


This output adds 32 bytes (128 WU).

Witness Data

The witness data consists of Data Pushes. I will not go into the details of Witness Programs in this answer. The witness program for this transaction is:

02 47 304402200760efedbcee3bbd913661fb40c364caed622b331ee3b5bc70ac25df2d3763d5022020efdb41ef325089d146eb48948b6aaec85c086fa38a3df4d2a51ee729645ebc01 21 02be338e0362fb01101a873a7502012cb82f7d9d303b4943fa0702829a763e4976


The Witness Data adds 107 bytes (107 WU).

Locktime

The locktime for this transaction is 2b550900 (611,627 in little-endian) and is used as the Block height at which this transaction's outputs can be spent. This adds 4 bytes (16 WU).

In total, this transaction is 565 WU. Converting to vB, that's 142 vB. With an Input Value of 0.02118172 BTC and a combined Output value of 0.02047172 BTC, the transaction fee is 0.00071 BTC (71,000 satoshi). The feerate of this transaction is 500 sat/vB. (also extremely high!)

Estimating Fees

With this knowledge, how does a wallet know how much to use as a fee given a feerate?
It's quite simple. See this answer for information on how a wallet handles this information given different address types. Your wallet estimates how much satoshi to set aside as fee based on the inputs, outputs, address types, and desired feerate before signing the transaction.

As for how wallets create transactions with the lowest fee possible, and how fee estimation algorithms that look at the current mempool work, they are wallet-dependent.