Help in NLGN Algorithm

HelloWorld · #1 (**permalink**) 07-12-2007, 10:09 PM

Anybody know about BIG-O-Algorithm, and Algorithm Analysis...? I'm confused at this, I'm trying to create a NLGN Algorithm, but I have no idea on how can I add N in fron t of the LGN

My LGN is currently a Binary Search, I'm still trying to figure out, hopefully anybody can help me with this, I've googled all of them are just sucks, expect those who took me to Stanford's technical paper which I don't even understand anything lol... Just need some examples how to create the pattern of these algorithm... Just confused with NLGN and N! (N Factorial) algorith...

TeraTask · #2 (**permalink**) 07-12-2007, 11:27 PM

I understand Big-O, but don't know what you're talking about for NLGN. Big-O, btw, is not an algorithm, but a construct for measuring the relative complexity of algorithms based on the number of calculations needed to be performed by the processor.

Edit: Just looked it up and what you mean is finding an algo whose complexity is O(nlgn) or n * log(n). According to ordernotation.html, mergesort and quicksort are of that order.

HelloWorld · #3 (**permalink**) 07-12-2007, 11:56 PM

Quote:

Originally Posted by TeraTask

I understand Big-O, but don't know what you're talking about for NLGN. Big-O, btw, is not an algorithm, but a construct for measuring the relative complexity of algorithms based on the number of calculations needed to be performed by the processor.

Edit: Just looked it up and what you mean is finding an algo whose complexity is O(nlgn) or n * log(n). According to ordernotation.html, mergesort and quicksort are of that order.

Haha, I just solved it lol...
I used Binary Search which is LGN, and put it inside a loop to form NLGN because if it's inside a loop, LGN will be multiplied by N to form LGN

here's what I got...

PHP Code:

      public void Logrithm() {

        int num[] = new int[n];

        for (int i = 0; i < num.length; i++) {

            num[i] = i + 1;

        }

        Random r = new Random();

        int key = num[r.nextInt(n)];

        t1 = System.currentTimeMillis();

        for (int i = 1; i <= n; i++) { // n

            Arrays.binarySearch(num, key); // LGN

        }

        t2 = System.currentTimeMillis();

        r4 = t2 - t1;

        System.out.println(r4);

    }

P.S to all of my class mates, don't copy it, use it to open your mind

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode