n by bylo takové, jaké si předepíšete.
U asymptotické složitosti snad jde o to, že ta složitost je stejná pro libovolně velké množství prvků.
Ano. Ale nemusí být splněno jedním algoritmem/obvodem, viz neuniformní třídy složitosti.
V popsáném případě by šlo o to, že pro každé n umíme najít třídící síť s <f(n) komparátorama a <g(n) hloubkou, kde f(n) je O(n log n) a g(n) je O(log n).