mohamed.mostafa's blog

Does That Search For Max Value In Array Run In O(Log N) ?
By mohamed.mostafa, 12 years ago, In English

public class Search {

static int []a ;
private static int tmax(int start, int end){
    if (end - start  == 0)
       return a[start];
    if (end - start== 1)
       return Math.max(a[start], a[start+1]);
    return Math.max(tmax(start, end/2), tmax(end/2+1, end));
}

public static void main(String[] args) {
    int []y = {10, 520, 300};
    a = y;
    System.out.println(tmax(0, a.length-1));
}

}

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +14 Vote: I do not like it

No.

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

You just made my day ^_^

No, this algorithm still touches every array element, so it works in at least O(n). Nice try, anyway.

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

Given an array a[1..N], answer a query without precalculation in time.
*trollface.jpg*

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Ever thought that you can't find max of N elements checking less than N of them?

(because each of elements should be compared at least once with some other)

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

    You can, if the array is sorted! ;)

    Upd. Moreover, if a[i] are 0s or 1s, and each a[i] is a fair coin toss, you can find a maximum in O(1) time at mean.

    Upd. Moreover, if a[i] is 32-bit integer, distributed uniformly and independently, you can find a maximum in O(1) time at mean, where O(1) = 2*2^32

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

      ...in O(1), by the way!

      Let us have a cake from the shelf since we are so clever boys! (c) old movie

      UPD: about UPD — and even moreover — let a[i] be of any type (even real), one can find max in O(N/2) if one knows the upper bound of numbers in this array beforehand. Particularly, if one already knows maximal number in array, one could find it once again in O(N/2). :D

      → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Moreover, this algorithm does not work at all. run it on the array with size 8.
if you replace end / 2 by (start + end) / 2, it will be O(n).

→ Reply