2

I am currently analyzing maximum subarray problem for both brute-force algorithm and divide and conquer algorithm (recursive).

Using the brute-force algorithm, the worst-case runtime is O(n^2). Using the recursive algorithm, the worst-case runtime is O(n*log(n)).

But the brute-force is actually faster for small input up to a certain constant, say k, so I thought to use the brute-force up to k, then recursive afterward.

I'm not sure how to analyze this one, i.e. by using the parameter n and k. (There's a similar problem for Insertion/Merge sort where it takes O(k^2*(n/k))=O(n*k), so I thought I could use the same result but...).

Let me try to reformulate, and lets use the theta-notation.

"What's the asymptotic runtime of the algorithm with brute-force within recursive (use n and k as parametre), where brute force is faster than recursive up to k = 50."

I have to include both parameter n and k on it, and recursion-tree is the only subject we have had so far to test these problems.

Improve this question
1
  • 6
    What's wrong with Kadane's algorithm? Commented Mar 10, 2012 at 21:46

1 Answer 1

Reset to default
3

Remember that big-O talks about the long-term growth rate of an algorithm. Formally, it says that for sufficiently large n, the behavior of one function is less than some constant multiple of another. This means that if you fix any choice of a constant k and then use the O(n2) algorithm for n ≤ k and the O(n log n) algorithm for all n > k, the overall runtime will be O(n log n), because as n grows sufficiently large the behavior of the algorithm depends purely on the behavior of the O(n log n) algorithm.

That said, you should look into Kadane's algorithm, an algorithm that uses dynamic programming to solve this problem in O(n) time, O(1) space, and just one pass over the array. It's almost certainly going to be faster (both practically and asympotically) than either of your approaches.

Hope this helps!

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

The brute-force is O(n^2). But for sufficiently small input, it's not O(n^2) since it's faster than the recursive.
@user1261561- The phrase "it's O(n^2) for small inputs" is not really meaningful here. Big-O necessarily describes long-term growth rates and completely ignores behavior on small inputs.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.