Evaluating time complexity
Some problems can be solved in many ways with different complexity.
For example, an array of n numbers can be sorted in O(n2) steps - (in a naive way) or in O(n*logn) steps (in an optimal way).
For 1000 numbers, naive sorting will require about 1000000 steps, whereas optimal sorting will need only 10000 - that's 100 times less.
For sufficiently big sets of input data our system can help to determine the complexity of the algorithm, based on execution time.
Sample challenge
We call the number 1+2+...+k the k-th triangular number and denote it T_k. The input of the program contains a certain number of positive integers. For each integer n provided at input, the program should compute and print to output the sum of the first n triangular numbers, T_1 + T_2 + ... + T_n.
For instance, for n=3 we have:
T_1 = 1
T_2 = 1 + 2
T_3 = 1 + 2 + 3
T_1 + T_2 + T_3 = 10
Example
input
1
3
10
output
1
10
220