Comment by kilotaras

Both 3n and 2n are linear, the broken conjecture is that you can't do better than linear.