doubts algorithm

Question

Determine the aspmptotic running time of $f(n)$.
int f(int n)
\{
int $x$;
if $(\mathrm{n}==0) x=1$;
else $x=f(\mathrm{n}-1)^{*} 2$;
$\mathrm{g}(x)$;
return $x$;
\}
void g(int m)
[
int $y$;
for ( $y=m ; y>0 ; y /=2$ );
\}

• A. $\Theta(\mathrm{n})$
  
• B. $\Theta\left(n^{2}\right)$
  
• C. $\Theta\left(2^{n}\right)$
  
• D. $\Theta$ (nlogn)

Comments

is it O(n²)

F(n) = time complexity of  G(n) 

G(n) = log(2) + log(4) + log(8).............+log(2ⁿ)

        = 1+2+3+4+5+..........+n =O(n²) 

---

answer given is O(n^2)

---

it should be D)

$T(n)=T(n-1)+ \log n$

$T(n)=\log n+\log n-1 +\log n-2 +...\log 2$

$T(n)=\log (n \times n-1 \times n-2 \times.. 2)=\log(n!)=\Theta (n \log n)$

---

but the complexity of function g changes with the value of x

Answer 1

else loop will be executed for (n-1) times

g(x) is also executed for (n-1) times as after every else g(x) should be executed. for better understanding draw the tree for some smaller input

again g(int m) function is executed for (1+logx) times

time complexity  wil be (n-1)(n-1)(1+logx) = O(n^2) where  (1+log x) can be omitted because of smaller value.

If I am wrong then plz correct me