# Beware the quadratic gas cost of memory allocation

Here we have a skeleton for an Auction contract. What do you think the gas cost of the alreadyBid function is in terms of the number of bidders? Would it be O(n)?

contract Auction {
struct Bid {
uint256 amount;
}

Bid[] public bids;

function bid() external payable {
require(msg.value > 0, "Must bid non-zero amount!");
Bid memory newBid = Bid(msg.value, msg.sender);
bids.push(newBid);
}

for (uint256 i = 0; i < bids.length; ++i) {
Bid memory bid = bids[i];
if (bid.bidder == bidder)
return true;
}
return false;
}

// Other auction functions down here...
}


If you’re not a seasoned Solidity engineer then it would be reasonable to think so… but lurking in Appendix H of the Ethereum yellow paper is a fact that’s easy to miss:

G_memory is fixed at 3 gas and is linear in the number of words the memory space has expanded to. But once the number of words exceeds 22 (a^2 > 512 => a > 22), it becomes quadratic, or O(n^2)!

Avoid unbounded for loops at all costs, especially when the operation that grows the number of iterations is out of your control (like executing a public bid function that’s callable by anyone).

Also, if you feel the need to use unbounded for loops then you might want to rethink your design. There’s often a way to do it better. We can avoid unbounded for loops in the auction contract by storing bids in a map instead of an array.

contract Auction {
struct Bid {
uint256 amount;
}

function bid() external payable {