# Solving recurrence by iteration, choosing base case

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

• There must be some base case already given to you, right? Otherwise, how can you apply the recurrence $i$ times? Commented Jan 10 at 22:38
• @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. Commented Jan 10 at 22:57

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).