# How can I find this code block's execution time t(n) and big O notation?

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

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$$.

• thanks so much! – user128778 Nov 22 '20 at 17:23