New answers tagged


You are correct that a term was omitted in the RHS of (2.3.10), but the final asymptotic bound $O(\phi^n)$ holds for the augmented RHS also. Perhaps it might be easier for you to see this if you just work out the solution for the nonhomogeneous recurrence relation from scratch rather than use Wilf's Theorem 1.4.1 on the epsilons, as shown below. Essentially,...


Obviously you can't say it's $O(N^3)$ because X might grow a lot faster than N. But you can't even say it's O (N x M x X), because you don't know how often the "list.append(count)" is executed and what the time complexity of that operation is.


As you have mentioned that $ N, M, X $ are variables, the time complexity would be $ O(N*M*X) $. A possible counter argument for the complexity not equal to $ O(N^3) $ is, what if the rate of increase of $ X $ is greater than rate of increase of $ N $ ?

Top 50 recent answers are included