Why it is $O(n)$ running time when we separate problems on n/2 subproblems each recursive call (and we continue to work on one side)

Question

So, I do not understand why it is $O(n)$ running time in the case when we have some $n$ elements and with each recursive call we separate our array by half and we continue working only on a one half (considering that each recursive call requires comparisons with each elements in a sub-array). Is it some sequence? How to express it in a mathematical way? I guess we can express this recurrence as $T(n) = T(n/2) + O(n)$

Thanks!

score 1 · Accepted Answer · answered Feb 15 '15 at 16:03

1

Because it is a geometric series. $$ T (n) \leq \sum_{k=0}^\infty \frac {cn}{2^k} = 2cn \in O (n)$$

answered Feb 15 '15 at 16:03

dalastboss

1,258

and where is O(n) on each recursive step? shouldn't it be the part of the equation? as I see we considered only T(n/2) here – UserMoon Feb 15 '15 at 17:33
1

$cn$ stands in for $O(n)$ here. $T(n) = T(n/2) + O(n) = cn + T(n/2) = cn + c(n/2) + T(n/4) = cn + c(n/2) + c(n/4) + ...$ – dalastboss Feb 15 '15 at 18:15

Why it is $O(n)$ running time when we separate problems on n/2 subproblems each recursive call (and we continue to work on one side)

1 Answers1