ERC-721 NFT standard in Blockchain / Solidity - Time & Space Complexity

Time Complexity: ERC-721 NFT standard

O(1)

Understanding Time Complexity

When working with ERC-721 NFTs, it's important to understand how the time to perform actions grows as the number of tokens increases.

We want to know how the cost of operations like transferring or checking ownership changes as more NFTs exist.

Scenario Under Consideration

Analyze the time complexity of the following simplified ERC-721 transfer function.

function transferFrom(address from, address to, uint256 tokenId) public {
    require(ownerOf(tokenId) == from, "Not owner");
    require(to != address(0), "Invalid address");

    _approve(address(0), tokenId);
    _owners[tokenId] = to;
    _balances[from] -= 1;
    _balances[to] += 1;

    emit Transfer(from, to, tokenId);
}

This code transfers ownership of a single NFT from one address to another.

Identify Repeating Operations

Look for loops or repeated steps that depend on input size.

• Primary operation: Accessing and updating ownership and balances for one token.
• How many times: Each transfer handles exactly one token, so operations happen once per call.

How Execution Grows With Input

The work done for transferring one token stays the same no matter how many tokens exist.

Input Size (n)	Approx. Operations
10	1 operation (one per token transfer)
100	1 operation (still one per transfer)
1000	1 operation (one per transfer)

Pattern observation: The time per transfer does not increase as more tokens exist; it stays constant.

Final Time Complexity

Time Complexity: O(1)

This means transferring a token takes the same amount of time no matter how many NFTs are in the contract.

Common Mistake

[X] Wrong: "Transferring a token gets slower as more tokens exist because the contract must check all tokens."

[OK] Correct: The contract uses direct mappings to find owners, so it looks up only the specific token without scanning others.

Interview Connect

Understanding how blockchain operations scale helps you explain gas costs and efficiency clearly, a useful skill for blockchain development roles.

Self-Check

"What if the contract stored all tokens owned by an address in an array and had to search it to find a token? How would the time complexity change?"

Practice

1. What is the main purpose of the ERC-721 standard in blockchain?

easy

A. To define a standard for unique non-fungible tokens (NFTs)

B. To create fungible tokens like cryptocurrencies

C. To manage smart contract deployment

D. To encrypt blockchain transactions

Solution

1. Step 1: Understand ERC-721's role

   ERC-721 is designed specifically for unique tokens, called NFTs, which are different from fungible tokens like cryptocurrencies.

2. Step 2: Compare with other token standards

   ERC-20 is for fungible tokens, while ERC-721 is for unique, non-fungible tokens.

3. Final Answer:

   To define a standard for unique non-fungible tokens (NFTs) -> Option A

4. Quick Check:

   ERC-721 = Unique NFTs [OK]

Hint: ERC-721 is for unique tokens, not fungible ones [OK]

Common Mistakes:

• Confusing ERC-721 with ERC-20 fungible tokens
• Thinking ERC-721 manages encryption
• Assuming ERC-721 handles contract deployment

2. Which of the following is the correct function signature to get the owner of an NFT in ERC-721?

easy

A. function getOwner(address token) public returns (uint256);

B. function ownerOf(uint256 tokenId) external view returns (address);

C. function owner(uint256 id) external returns (address);

D. function tokenOwner(uint256 tokenId) public view returns (string);

Solution

1. Step 1: Recall ERC-721 standard function names

   The standard defines ownerOf with a uint256 tokenId parameter returning an address.

2. Step 2: Check function visibility and return type

   The function is external view and returns an address, matching function ownerOf(uint256 tokenId) external view returns (address); exactly.

3. Final Answer:

   function ownerOf(uint256 tokenId) external view returns (address); -> Option B

4. Quick Check:

   ownerOf(tokenId) returns owner address [OK]

Hint: Look for 'ownerOf' with tokenId returning address [OK]

Common Mistakes:

• Using wrong function names like getOwner or tokenOwner
• Incorrect return types like string instead of address
• Missing view or external keywords

3. Given the following Solidity snippet, what will be the output of ownerOf(1) if token 1 is owned by address 0xABC...?

contract MyNFT is ERC721 {
    mapping(uint256 => address) private _owners;
    
    function ownerOf(uint256 tokenId) public view override returns (address) {
        return _owners[tokenId];
    }

    function mint(address to, uint256 tokenId) public {
        _owners[tokenId] = to;
    }
}

medium

A. 0x0000000000000000000000000000000000000000

B. Compilation error

C. 0xABC...

D. Function does not return anything

Solution

1. Step 1: Understand the mint function effect

   The mint function sets the owner of tokenId to the given address in the _owners mapping.

2. Step 2: Check ownerOf return value

   The ownerOf function returns the address stored in _owners[tokenId]. If token 1 was minted to 0xABC..., it returns that address.

3. Final Answer:

   0xABC... -> Option C

4. Quick Check:

   ownerOf(1) = minted owner address [OK]

Hint: ownerOf returns stored owner address from mapping [OK]

Common Mistakes:

• Assuming default zero address if not minted
• Thinking function has no return
• Confusing compilation errors with runtime behavior

4. Identify the error in this ERC-721 transfer function snippet:

function transferFrom(address from, address to, uint256 tokenId) public override {
    require(ownerOf(tokenId) == msg.sender, "Not owner");
    _owners[tokenId] = to;
}

medium

A. The require should check if msg.sender is approved or owner, not just owner

B. The function should not override transferFrom

C. The _owners mapping should not be updated

D. The function is missing a return statement

Solution

1. Step 1: Check transferFrom permission logic

   ERC-721 requires that the caller is either the owner or approved to transfer the token, not just the owner.

2. Step 2: Identify missing approval check

   The code only checks if msg.sender is the owner, missing approval checks, which can block valid transfers.

3. Final Answer:

   The require should check if msg.sender is approved or owner, not just owner -> Option A

4. Quick Check:

   transferFrom needs owner or approved check [OK]

Hint: Check both owner and approved in transferFrom require [OK]

Common Mistakes:

• Only checking owner without approval
• Forgetting to override transferFrom
• Not updating ownership mapping

5. You want to create an NFT contract that allows only the original minter to burn their token. Which ERC-721 function should you override and what check should you add?

hard

A. Override mint and check if msg.sender is approved

B. Override transferFrom and check if msg.sender is the owner

C. Override approve and check if msg.sender is the contract owner

D. Override _burn and check if msg.sender is the original minter

Solution

1. Step 1: Identify burn function in ERC-721

   The _burn internal function handles token destruction in ERC-721 contracts.

2. Step 2: Add ownership check for burning

   To restrict burning to original minters, override _burn and add a check that msg.sender matches the original minter address stored during minting.

3. Final Answer:

   Override _burn and check if msg.sender is the original minter -> Option D

4. Quick Check:

   Burn control = override _burn + minter check [OK]

Hint: Control burn by overriding _burn with minter check [OK]

Common Mistakes:

• Trying to control burn in transferFrom or approve
• Not storing original minter address
• Checking approval instead of minter for burn