0
$\begingroup$

I have this assignment for a class and we're beginning to learn time complexity. I have to find create a Java program that finds the stability indices of an array. Stability index being defined as a[0] + a[1] + ... a[i-1] = a[i+1] + a[i+2]+ ... a[n-1]. Essentially if you sum every element left of the index and every element right of the index(excluding the element at the index itself) and the two sums are equal, it is a stability index.

I believe its complexity is O(n^2) since I have nested loops both with worst case size of n. I'm having difficulty understanding how to make this more efficient. I thought perhaps there would be a way to calculate two different arrays of sequential sums. One would be increasing from index 0 and the other decreasing from the last index. Then compare the two values, but I'm not sure how to do this without nested loops.

Not looking for answers, just a push in the right direction.

EDIT: I made an improvement to O(N)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Assume you have the sum $a[1] ... a[i - 1]$ and $a[i+1] ... a[n - 1]$. You can directly check the "stability" for index $i$. Think of how much additional computation you need to calculate the "stability" for index i + 1. In an $O(N^2)$ solution you would need $O(N)$ additional work by just recomputing the sum again. Is there something better you can do to reduce this to $O(1)$ so that the overall runtime reduces to $O(N)$.

Basically can you reuse some information that you already calculated before?

Improve this answer
$\endgroup$
3
  • $\begingroup$ Hey! I think I used what you told me and made an improvement to O(N) in the algorithm! i added the update to my original post! If possible, could you double check that for me? $\endgroup$
    – Typhus
    May 21, 2018 at 4:06
  • $\begingroup$ I should have mentioned the actual code itself is irrelevant on this website as well as checking if your logic is exactly correct. As long as you believe your algorithm is correct and test or prove it I believe you should be fine. Hope I was helpful $\endgroup$
    – sunnytheit
    May 21, 2018 at 4:29
  • $\begingroup$ absolutely, I really appreciate it! thank you! $\endgroup$
    – Typhus
    May 21, 2018 at 4:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.