Hi,

I need some help with my programming assignment.

Say i have an array of numbers like {-1,0,2,4,5,6,7}, i.e a total of 7 numbers starting from index 1 to 7. I need to find how many no.s have a value equal to their index.

In the above example 4 numbers have values equal to their indexes(they are 4,5,6,7 located in the 4th,5th,6th and 7th index positions respectively). My task is to first translate the above said array into an appropriate data structure and then using that data structure am supposed to find the solution and all this has to be done in O(log n) complexity. I am not sure how to get started with this assignment. I would really appreciate if some one could help me get started. Btw am also not supposed to use the JAVA API.

Thanks a million

This post has been edited by vvinod1310: 2 Sep, 2008 - 10:14 AM

ahhh yes....it's school time.


Dream.In.Code has a policy by which we prefer to see a good faith effort on your part before providing source code for homework assignments. Please post the code you have written in an effort to resolve the problem, and our members would be happy to provide some guidance. Be sure to include a description of any errors you are encountering as well.

Please post like this:

Thank you for helping us helping you.

Without giving you the solution, constructing an algorithm that performs with O(log n) complexity usually means you're dealing with a divide and conquer algorithm. Try to analyze this problem for a while.

* What can you say about the input domain?
* How can you break down this problem into subproblems (preferably 2 problems of equal size)?
* Is it actually possible to find a solution that performs in O(log n)? (Always consider the worst case)

I actually think you're misinterpreting the assignment because the answer to the third question is No! In order to find the answer you need to consider all numbers in the array so WC complexity is O(n).

I assume you're working with a black-box (this black-box is not really available) which can answer you true/false to the question: Are there k numbers that are equal to their index?
With this kind of black-box, you could find the correct answer in O(log n). However, the same black box would let you solve the TSP (Travelling Salesman Problem) in polynomial time and you'd be rich like a troll.

This post has been edited by Gloin: 2 Sep, 2008 - 01:31 PM

Hint: Search for "for loop"-s.

If the solution has to be O(log n) you can't just for-loop since it will give you O(n) complexity.

Correct me if I'm wrong, but you can't do that in complexity less than O(n).

You have to check every single number in array => n.

This post has been edited by Unknown Hero: 2 Sep, 2008 - 03:00 PM

Yes, that is correct (At least if you consider only worst case. In amortized complexity you can make it in O(log n)). I already stated it in the explanation above.

No, actually it can't even be achieved with amortized complexity. Unless you assume the input is ordered and distinct (disjoint) (probably have to add more constraints than that as well). And even then I'm not certain.

In conclusion, you can't solve this problem in O(log n)

You can find a solution in amortized O(log n) time if the input is sorted but then sorting takes O(n log n) which would then be the bound.

Like suggested, you should use a divide & conquer algorithm. It will let you discard some of the numbers that can't possibly match their index.