The second solution works in linear time only if one assumes that multiplication is a constant time operation. But is it really? If you look at how a processor does multiplication it becomes clear it is a O(log n) operation where n is one of the numbers being multiplied. Thus, the second solution is probably a O(nlogn) solution.