doubts algorithm

Question

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