How do I find out the time complexity for:
T(n) = 1 if n <= 4
1 + T(n-4) for n > 4
n is even
Any help is appreciated.
Printable View
How do I find out the time complexity for:
T(n) = 1 if n <= 4
1 + T(n-4) for n > 4
n is even
Any help is appreciated.
Though I've studied math I'm not familiar with the term "time complexity", maybe I know the Spanish version under quite different words, but I'm interested...Quote:
Originally Posted by The Hobo
I suppose he means this http://www.csc.liv.ac.uk/~ped/teacha...r/complex.html for optimizing his coding.
You reduce n by a fixed amount until you reach a value <4, so that is O(n) steps. Or do you mean that T(n) is the complexity and you want to reduce it to a big oh notation?
I know it goes something like:
But I don't know why, or what my result is supposed to look like...and I can't find anything on the web to help. Any have any ideas?Code:T(N) = 1 + T(N - 4)
T(N - 4) = 1 + T(N - 8) T(N) = 1 + (1 + T(N - 8))
T(N - 8) = 1 + T(N - 12) T(N) = 1 + (1 + (1 + T(N - 12)))
You should look at it the other way around:
T(n) = 1 for 0<n<=4
T(n) = 2 for 4<n<=8
T(n) = 3 for 8<n<=12
You can now substitute T(i):
a = T(n) = 1 for 4*a-4<n<=4*a
b = T(n) = 2 for 4*b-4<n<=4*b
c = T(n) = 3 for 4*c-4<n<=4*c
So, given T(n) you can caluculate the range of minn<n<=maxn:
minn(T(n)) = 4*T(n)-4
maxn(T(n)) = 4*T(n)
Now to reverse this function you need to map a range to a single number, this can be done with the ceil function (roundig up) and a division:
T(n) = ceil(n/4)