The square size increases as 3x3 5x5 7x7 and so on
Eg :
Sum of first square is 12
Sum of second square is 60
I was able to find a linear solution to this (the sum of a specific square), but is there a constant or anything less than O(n) that can be used to evaluate the required sum.
If you can get the sum of a specific square k as polynomial of k, some it up from 1 to n to get the polynomial solution of original problem, thus evaluate it in O(1). This link may help: https://en.wikipedia.org/wiki/Sums_of_powers