A question I am to answer wants me to find the big O of a recurrence, I am doing it with the iteration method. For the base case, which we get after applying the recurrence $i$ times, can we make this any number as long as we assume it will be in constant time? Such as $T(5)$, $T(100)$ etc. I can't give anymore info to the question as it's an assignment. Thanks
$\begingroup$
$\endgroup$
2
-
$\begingroup$ There must be some base case already given to you, right? Otherwise, how can you apply the recurrence $i$ times? $\endgroup$– Inuyasha YagamiCommented Jan 10 at 22:38
-
$\begingroup$ @InuyashaYagami I can assume for a constant size it runs in constant time, so I'm thinking if I just assume it to be a given value. The variable i is just a 'placeholder' which we could find given the assumed base case, that is my reasoning. $\endgroup$– user438409385Commented Jan 10 at 22:57
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Well, obviously $T(1),T(2),\dots,T(100)$ are all integers. So, let $c=\max(T(1),T(2),\dots,T(100))$. $c$ is obviously some integer, so it is a constant. So yes, all of those base cases are at most a constant.
In practice, we often assume that $T(1)=1$, as usually multiplying it by a small constant doesn't change anything about the asymptotics (though of course there are strange cases where this might not hold).
$\begingroup$
$\endgroup$
If you have a recurrence that doesn’t apply to the case n = 1, then it would be correct to assume T(1) = c, for some unknown c, and resolve the recurrence based on that; this would be useful if you are interested in actual and not just asymptotic values.
Or you can say that T(1) is O(1) and go from there. If the recurrence is problematic for small n, then you can also assume for example max (T(1), T(2), …, T(100)) = O(1).
