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
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.
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.
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.
Wow people just start following a rating>blue coder like sheep. Tell me the reason of downvote
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:
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.
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.
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: