Results 1 to 4 of 4

Math Help - a matrix problem

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    15

    a matrix problem

    The problem is to find a local maximum value in an NxN matrix in O(n) time. A locally maximum value in a matrix is the one who's value is greater than the values of its neighbours i.e. the North, South, East and West elements. (So the elements lying on its diagonals are not its neighbours).

    An algo that came to my mind is that, you start with the element at position (1, 1). Compare it to its neighbours. If it is greater than them, we're done. If not, we pick the largest element out of its neighbours, and repeat the process.

    How do I show that this can be done in O(n) time?
    Last edited by mathdigger; February 19th 2011 at 08:55 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by mathdigger View Post
    The problem is to find a local maximum value in an NxN matrix in O(n) time. A locally maximum value in a matrix is the one who's value is greater than the values of its neighbours i.e. the North, South, East and West elements. (So the elements lying on its diagonals are not its neighbours).

    An algo that came to my mind is that, you start with the element at position (1, 1). Compare it to its neighbours. If it is greater than them, we're done. If not, we pick the largest element out of its neighbours, and repeat the process.

    How do I show that this can be done in O(n) time?
    The problem as I see it is that the entries in the matrix may look like this:
    Code:
    1 2 3 x x x x x x x x
    o o o o o o o o o o x
    x x x x x x x x x o x
    x o o o o o o o x o x
    x o x x x x x o x o x
    x o x o o o x o x o x
    x o x o x x x o x o x
    x o x o o o o o x o x
    x o x x x x x x x o x
    x o o o o o o o o o x
    x x x x x x x x x x x
    Here, the o's represent zeros, and the "snake" of x's represents an increasing sequence of numbers starting with 1, 2, 3 as shown, and continuing to increase as the snake coils towards the centre of the matrix. Your algorithm will require you to move along the entire length of the snake, which has O(N^2) elements in it.

    In fact, the element at the end of the snake constitutes the only local maximum in the entire matrix, and I don't see any general procedure for locating it in less than O(N^2) moves. (But then I know nothing about algorithms.)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2010
    Posts
    15
    hmm you're right. Ok, what if I put this extra condition that all the entries of the matrix are distinct real numbers > 0 ? Do you think that can help achieve O(n) time somehow?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by mathdigger View Post
    Ok, what if I put this extra condition that all the entries of the matrix are distinct real numbers > 0 ? Do you think that can help achieve O(n) time somehow?
    That won't help. In the example that I gave above, just replace the o's by distinct positive numbers all less than 1. You are still left with that long snake of increasing numbers.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Matrix Problem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: May 14th 2011, 10:11 PM
  2. Replies: 0
    Last Post: December 2nd 2010, 03:40 PM
  3. Matrix Problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 22nd 2010, 11:26 PM
  4. Matrix problem, help please
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 5th 2009, 02:48 AM
  5. Help with Matrix Problem
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: October 26th 2008, 05:57 PM

Search Tags


/mathhelpforum @mathhelpforum