Question

求教时间复杂度的计算：O(1)+O(2)+...+O(N-1)+O(N)=?O(1)+...+O(N/4)+O(N/2)

Answer 1

第一个：1+2 + ...+ N = N(N+1)/2 于是去掉常量和低阶的得到O(N^2)

第二个：1 + ...+ N/4 + N/2 + N = 2N,于是为O(N)