Average is useful but is Little o relevant outside of very low latency things like games? If the input is small it will run fast for any solution anyway.