Fibonacci Series Complexity

Question

PLEASE EXPLAIN HOW TO APPROACH THESE KIND OF PROBLEMS

Comments

$n^2$ is another number. it is given the time complexity to find $F_n$  as O(log(n)) for any n. $F_{n^{2}}$ is $F_{N}$ for N=$n^2$ having complexity O(log(N)) . here option C and A are the same with option A being more simplified version of option C.

Answer 1

$F_k$ is the $k^{th}$ number, and can be calculated in $O(\log k)$.

Similarly, $F_{n^2}$ is the $(n^2)^{th}$ number, and hence can be calculated in $O(\log n^2)$, i.e $= O(\log n)$.

Both A and C are correct in terms of mathematical notation of Order of growth.

Order notation denotes a set of functions, and both above denote the same set.

When we talk about the complexity of algorithms, we keep it as simplistic as possible, avoiding unnecessary details.

Answer 2

Answer will be $O(log(n^{2}))$.

Here, $log(n^{2}) = 2logn$ which leads to $O(2logn) = O(logn)$ as you drop the constants in Big-Oh notation.

So, both A and C.

Note, too, that $O(log(n))$ is exactly the same as $O(log(n^{c}))$. The logarithms differ only by a constant factor, and the big O notation ignores that. Similarly, logs with different constant bases are equivalent.