I'm doing some introductory algorithm analysis practice problems, and am still a bit shaky on some aspects of it. I've taken a shot at the exercise below, but don't have an answer key. Comments are my own work. I was wondering if anyone with experience in this area would be willing to look at my attempt, and let me know whether or not I've approached it correctly. Any help is appreciated!
"Give the asymptotic worst case running time of the following pseudocode as a Big-Theta expression."
procedure Sum(n)
S ← 0 //1 for assignment
k ← n //1 for assignment
while k ≥ 1 do //O(log n)
for i = 1, 2, . . . , n do //n*O(log n)
S ← S + n //(1 for assignment + 1 for addition)*n*O(log n)
end for
k ← k/2 //1 for division + 1 for assignment
end while
return S //1 for return
end procedure
//Total is 1+1+O(log n)+nO(log n)+2nO(log n)+2+1 =
//5+(3n+1)*O(log n) =
//ϴ[(3n+1)log n]
Overall, the approach is good, as well as the final result, but there are some minor aspects that can be corrected:
since you are interested in the Big-Theta class it would be best to use it from the beginning. This would prevent the final conversion from Big-O to Big-Theta, i.e. the step doing 5+(3n+1)*O(log n) = ϴ[(3n+1)log n]), which is not true in general.
The k ← k/2 //1 for division + 1 for assignment is inside the while k ≥ 1 do //O(log n) loop, thus it should be multiplied with log(n) when considering it for the total complexity. Nevertheless, the final result was still correct, because the complexity is dominated by the work done in the innermost loop.