CODEWITHSUNDEEP
recursionbig-o
hopelessmuffins
hopelessmuffins

Reputation: 315

What is the big-O of this recursive algorithm

We have a problem of size n

An algorithm that recursively solves a subproblem of size n − 1 and performs a linear amount of work on the solution.

I tried using plug n chug and found that the big-O is n, linear, but that does not seem right to me. What else could I try?

Upvotes: 3

Views: 441

Answers (2)

displayName
displayName

Reputation: 14379

The formula for the recursion mentioned by you is:

  • T(n) = T(n-1) + O(n)

It implies that:

T(n) = kn + k(n-1) + k(n-2) + .. + k, which is equal to k * n * (n + 1) / 2.

So, the complexity of the algorithm is O(n2).

Upvotes: 2

Mac O'Brien
Mac O'Brien

Reputation: 2907

The people at Mathematics Stack Exchange will probably be able to do this better than I can, but I'll give it a shot.

The description of the algorithm is ambiguous, so there are two possibilities:

  1. The algorithm performs a constant amount of work for each subproblem. In this case, the algorithm will in fact run in O(n) time (technically 2n, but constant factors are ignored).
  2. The algorithm performs a linear amount of work for each subproblem. In this case, you're looking at a linear loop that does linear work each execution. n executions, n work per execution = O(n^2). Obviously each successive execution does less work, and this would manifest in a recurrence relation solution as something around T(n) = (1/2)n^2, assuming I remember that pattern of problem right.

Upvotes: 2

Related Questions