Does it cost more storage? For the transaction verification, to which extent bigger blocks make it more computational intensive? In terms of computational complexity, is the verification process a O(n) computation or anything else?
Short answer: For big players the cost is mostly negligible.
Longer answer (independent of the current block size debate):
Hard Drive Cost: A bigger block will take up more disk space. Right now the block size is limited to 1 MB. If the block size is increased to 2 MB and assuming all blocks are always being filled to the max size then you will need about twice the hard drive space to store the same amount of 2 MB blocks as you needed for 1MB blocks.
Network Bandwidth Cost: If block size is increased, a full node has to relay a bigger size block. Sending and receiving more data will have an impact on cost as well.
Real Time Computational Cost: A full node has to hash a block and verify that the hash has n amount of leading zeros. Increasing the block size will result in hashing a larger amount of data which increases verification time.
Big O Complexity: Big O would depend on whatever the Big O is for sha256.