Return to Question

deleted 119 characters in body

Source Link

edited Jul 28, 2015 at 14:17

I was asked to figure out the time complexity analysis for the following recurrence relation T(n) = 4*T(n-1) + c.

Basically, I did a replacement.. T(n-1) = 4 * T(n-2) + c and so on..

T(n) = 4^k T(1) + c(1 + 4 + 4^2..4^(k-1))

I worked it out as O(4^k) Would like to know if this is right or wrong?

PS: I am very sorry if this question does not belong here , I honestly didnt know which other stack exchange to ask.

I was asked to figure out the time complexity analysis for the following recurrence relation T(n) = 4*T(n-1) + c.

Basically, I did a replacement.. T(n-1) = 4 * T(n-2) + c and so on..

T(n) = 4^k T(1) + c(1 + 4 + 4^2..4^(k-1))

I worked it out as O(4^k) Would like to know if this is right or wrong?

PS: I am very sorry if this question does not belong here , I honestly didnt know which other stack exchange to ask.

I was asked to figure out the time complexity analysis for the following recurrence relation T(n) = 4*T(n-1) + c.

Basically, I did a replacement.. T(n-1) = 4 * T(n-2) + c and so on..

T(n) = 4^k T(1) + c(1 + 4 + 4^2..4^(k-1))

I worked it out as O(4^k) Would like to know if this is right or wrong?

Source Link

asked Feb 3, 2015 at 13:41

Time complexity analysis for recurrence relation

I was asked to figure out the time complexity analysis for the following recurrence relation T(n) = 4*T(n-1) + c.

Basically, I did a replacement.. T(n-1) = 4 * T(n-2) + c and so on..

T(n) = 4^k T(1) + c(1 + 4 + 4^2..4^(k-1))

I worked it out as O(4^k) Would like to know if this is right or wrong?

PS: I am very sorry if this question does not belong here , I honestly didnt know which other stack exchange to ask.