Results 1 to 9 of 9
Thread: O(log n) algorithm help !!!!!!
 09092008, 08:59 AM #1Member
 Join Date
 Sep 2008
 Posts
 5
 Rep Power
 0
O(log n) algorithm help !!!!!!
Hi,
I have a problem at hand and i kinda need a head start in the same.
I have an array with some values inside and basically i need to check if the array (index value+1) == the actual value in that index and if so, i need to increase a counter.
int a[] = {1, 0, 2, 4, 5, 6, 7}
and the result shud be 4 for this because ther are 4 elements in this array which satisfy the condition... as, starting from index a[3] till a[6]....the value of index is equal to (index+1)
like a[3] = 4
a[4] = 5
a[5] = 6
a[6] = 7
but the catch is to do it in O(log N)...and not o(n).....can someone plz gimme a head start into solving this problem??
thnx in advance...plz reply soon...its urgent :) thnk yu
 09092008, 11:37 AM #2
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,372
 Blog Entries
 1
 Rep Power
 19
Do you want to increase the value after condition is satisfied?
 09092008, 01:51 PM #3do it in O(log N)...and not o(n).
 09092008, 02:46 PM #4Member
 Join Date
 Sep 2008
 Posts
 5
 Rep Power
 0
There is no need for increase of any value other than a counter which keeps track of the number hits(condition satisfied)...
So,is there a solution in O(log n) for this problem .... i am guessing that it is a possible for sure as this is part of a project work i am involved in and the specs required an O(log n) solution for this very same problem...
is it possible??
thnx...
 09092008, 02:49 PM #5Member
 Join Date
 Sep 2008
 Posts
 5
 Rep Power
 0
O(n) is linear...for example...finding an item in an unsorted list...
O(log n) logarithmic like Finding an item in a sorted array with a binary search...
the the sort range half themselves over every iteration, so to speak in the case of O(log n)....
so given that...is the problem i posted solvable in O(log n) ??
thnx...
 09092008, 03:23 PM #6Member
 Join Date
 Sep 2008
 Posts
 5
 Rep Power
 0
Hi,
sorry for the confusion earlier....
ONE important point to note is that the array is alwayz assumed SORTED...in ascending order....
This being the case... is it possible to reach (log n)... i do understand that there is a need to go thru the entire array to arrive at a result(thats the obvious algo which i d think of)....but the specs given for this assignment is that it has to be done in O(log n)....
let me give a more clearer view to the problem, i hav not been explicit , i am sorry...
Suppose there is some number N, and there are 7 elements in another array. Each element in the array is given another spl number(one number per element)....say K ...then we hav to form the array by adding the first given value of N (100) to the spl number K for first array(A) element. The resultant value is the first value of our input array(B). and this value now replaces for the new N. The 2nd element of the input array(B) = first value of array(B) + spl number K for 2nd element of array(A) and so on...
eg. N = 100 (intial value)
Array A: {99, 1, 2, 2, 1, 1, 1} [differnt K values]
then array B becomes
{ 1, 0, 2, 4, 5, 6, 7}.... [explanation 100 + 99 = 1 > 1 + 1 = 0> 0+2= 2>2+2 =4 >4+1=5>5+1=6>6+1=7 ]
it is this array that we have to chk for the condition i posted earlier... (index+1 = value of index)
At any point of time we can find the array A values for each array B value by subtracting the 2 adjacent index values...i was able to infer this now...does this help with a solution?
Given this... is it now possible to compute in O(log n) ???
 09092008, 04:17 PM #7
How does your question relate to Java?
It looks like you are looking for an algorithm.
When you get the algorithm, post it and we'll help you write it in java.Last edited by Norm; 09092008 at 04:30 PM.
 09092008, 04:21 PM #8Member
 Join Date
 Sep 2008
 Posts
 5
 Rep Power
 0
yes...but i am implementing the algorithm in java ...
help please.
 09092008, 05:12 PM #9
Similar Threads

Need help  using algorithm statements
By javanewbie in forum New To JavaReplies: 2Last Post: 07232008, 11:20 AM 
Help with algorithm in java
By coco in forum AWT / SwingReplies: 1Last Post: 08012007, 06:45 AM 
Help with algorithm
By susan in forum New To JavaReplies: 1Last Post: 07132007, 10:26 PM 
Help me with this algorithm
By Marcus in forum Advanced JavaReplies: 3Last Post: 07022007, 01:30 PM 
Help with Algorithm
By Daniel in forum Advanced JavaReplies: 2Last Post: 07022007, 05:51 AM
Bookmarks