Give a tight asymptotic run time analysis theta notation for

Give a tight asymptotic run time analysis (theta notation) for the following pseudo-code snippet: sum leftarrow 0 for i leftarrow 1 to n do for j leftarrow 1 to [n/i] do sum leftarrow sum + ary[i]

Solution

sum <- 0
for i<-1 to n do
   for j<- 1 to [n/i] do
       sum <- sum + ary[i]

Here time complexity:

Inner for loop runs for i=1,2,3..,n

   n/1 + n/2 + n/3 + n/4 + n/5 + ...+ n/n times

= n(1 + 1/2 + 1/3 + 1/4 + .... )

Note: we have harmonic series here

= n*logn (approx)

= O(nlogn)