0
$\begingroup$

Hello I am a CSE student and this question was in my homework.

double fact(long i)
{
if (i==1 || i==0) return i;
else return i*fact(i-1);
}

funcQ2()
{
for (i=1; i<=n; i++)
sum=sum+log(fact(i));
}

I thought it is O(n^2) but can the bottom function's log function call make it O(n^3)? I am not sure

Thanks in advance

$\endgroup$
0
$\begingroup$

fact(n) runs at $O(n)$.

So, each iteration of funcQ2 runs at $O(i)$, assuming log runs at constant time. (There are several algorithms to calculate the log)

Then the question turns into calculating $\sum_{i=1}^n O(i)$, and the answer is $O(n^2)$.

Now suppose your log(n) runs at time $O(f(n))$.

Then the answer to your question should be $\sum_{i=1}^n O(f(i))$. You should calculate that on your own as I don't know the $f$.

$\endgroup$
  • $\begingroup$ thanks so much! $\endgroup$ – user128778 Nov 22 '20 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy