aman_naughty's blog

Time complexity help Max Product Subarray
By aman_naughty, history, 5 years ago, In English

I have solved the maximum product subarray problem using divide and conquer. Can someone help me with the time complexity of my solution . Whether it is O(log(n)) or O(nlog(n)) . I am confused please help.

code

My approach is either the max product subarray lie in left half or right half or be passing through the middle. In the third case the answer can be formed from max of following:

left part's maximum suffix product * right part's maximum prefix product

left part's minimum suffix product * right part's minimum prefix product

as elements can be negative

  • Vote: I like it
  • -20
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

log(n) < n < n*log(n). It's important to know this. If you don't know what these runtimes mean, knowing what the runtime is is meaningless.

If you know how segment trees work, they create 2*n nodes total. Each index is covered by log(n) nodes. If you need to iterate over all the indecies a node covers to create it, your segment tree creation will be n*log(n). If you can create a node in constant time (plus the time to create its children) then creating the segment tree takes 2*n time.

To be clear, I am using 2*n because you create n + n/2 + n/4 + ... nodes, which is roughly 2*n.

It looks like you are calling the method in the same way one would create a segment tree, so your algorithm isn't log(n) or n*log(n), it's O(n). Your recursion only goes log(n) deep though, so you use O(log(n)) memory.

→ Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Also, analyzing this runtime is way easier than coming up with this solution, assuming your solution is correct. If you really did come up with the solution, whoever is interviewing you will probably be very likely to be suspicious that you didn't come up with the solution yourself if you can't explain how it works.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it -20 Vote: I do not like it

    I came up with the solution myself as I have already solved maximum sum subarray using divide and conquer. Also this solution is correct as it is accepted on interviewbit. Just because I am not a colored coder you assumed that I could not come up with this solution that's disappointing. Also why are people downvoting my blog. I am not so well versed with time complexity that's why I asked such a question. I do know that log(n)<n<n*log(n)

    I came up with this solution as I have solved similar problems in case of segment trees namely : GSS3 SPOJ

    I can very well explain how it works just the time complexity part confused me.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it -17 Vote: I do not like it

      Wow people just start following a rating>blue coder like sheep. Tell me the reason of downvote

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        It is very unusual to see someone who can't understand time complexity but can write such algorithms. Usually if people don't understand time complexity, they wouldn't even see the advantage of using Divide & Conquer over doing it straightforward like this:

        1. iterate over each possible subarray and calculate their product;
        2. print out the largest product you have seen.

        This has worse time complexity but it is much simpler to come up with. If someone didn't understand time complexity, I'd expect them to write this.

        Just because I am not a colored coder you assumed that I could not come up with this solution that's disappointing.

        I won't deny that people tend to judge others because of their color, but on the other hand this is just speculation on your part and an unfair accusation. I point out that SecondThread didn't even say you didn't write this yourself, they only said that it might look suspicious. You got needlessly defensive.

        I came up with the solution myself as I have already solved maximum sum subarray using divide and conquer.

        I came up with this solution as I have solved similar problems in case of segment trees namely

        Also again, I'm not saying this is the case, but some people might interpret this as you saying "yes, I 'solved' this problem because I have seen someone's solution to a very similar problem".

        Why did your blog get downvoted? For one thing, people dislike it when low-rated coders ask questions that they consider "stupid". That is unfortunate reality and you can't change it. However it's not always the case that when a low-rated user asks a question, it gets downvoted (example). There are many things you can change if you want people to not downvote your questions and be more willing to help you:

        • Get rid of the pushy attitude.
        • Format your blog well. Most importantly, put your code in a code block. And make the rest look nice too. For example I recommend using LaTeX for the formulas and big-O notation. Also, put a period in the end of every sentence; notice that there is no space before the period. Make sure your sentences are well-formed and clear. This isn't instant messaging, you should take 2 minutes to make sure the blog looks nice and clean.
        • Show that you have made your best effort to answer and still failed. This is really important — people are much more likely to help someone if they show that they're genuinely trying to learn, not just get a quick answer. In your case, explain why you think the complexity might be $$$\mathcal{O}(\log n)$$$ and where your confusion comes from. (See? This formula looks much nicer).
        → Reply