What is Log(n)?

03-23-2008, 03:25 PM	#1
darkwulfv	People (mainly Griffin and the other programming nuts) will sometimes mention "Log(n)". What is Log(n)? If it's something you learn in mathematics @ school, then it's no wonder I haven't heard of it. (My school has yet to properly teach me trigonometry, and I'm supposedly learning content from the 10th grade curriculum).

03-23-2008, 03:28 PM	#2
TheSecretArts	Log(n) I believe is in reference of binary operations since they are assumedly talking about programming My Advanced Algebra 2 class just started logs.

03-23-2008, 03:35 PM

Jazradel

A log is a function where:
a^y = b
y = loga(b)
http://en.wikipedia.org/wiki/Logarithm start with that to learn the principle and continue with http://en.wikipedia.org/wiki/List_of...mic_identities to learn how to use them. And yes, it should be something you learn at school but they're not really hard to grasp.

Griffen, etc are probably referring to algorithm performance, however. http://en.wikipedia.org/wiki/Run-time_analysis has details.

03-23-2008, 04:32 PM

Taur

Very basically, log is a math function that tells you what exponent you have to raise 10 to in order to get that function. For example, log 100 = 2 because 10^2 = 100.

The most important property of logs is that if you have say log (10^2), you can bring the 2 down so you get 2log10. This means (like Jazradel said) if yo uhave an equation

a^y = b
you take the log of both sides
log a^y = log b
y log a = log b
y = log b/log a
y = log subscript a b

Now you divide a log B by log A you say it as log B to the base (A) or it is written as log (subscript a) b.

Now uh, that's a crash course in what logs do, I believe you learn it in late gr. 11 to early gr. 12 it matters on where you are. In China you probably learn it in grade 3.

Ah whoops, just realized you were talking about it in programming... I didnt want to delete all my hard work though so I posted it anyways :P

03-23-2008, 04:40 PM	#5
Captain Griffen	Basically, if efficiency is O(n), then double the number of objects, double the time taken (processor wise). If it is O(log(n)), then the square of the number of objects requires double the time. IE: If it takes 1 second with 10 objects, it takes 2 seconds with 100 objects, 3 seconds with 1000 objects, etc., as opposed to 100 seconds.

03-23-2008, 04:44 PM	#6
Salbrismind	Specially the function Log(n) assume a base of 10 thus if n == 100 then you should get 2. n = 100 10^2 = 100

03-23-2008, 04:59 PM

Vexorian

Examples:

JASS:


...
    private integer n
    private handle array H
    private integer array V
    
...

... takes handle h returns integer
local integer i=0

    loop
           exitwhen i==N
           if (H[i]==h) then
                  return V[i]
           endif
           set i=i+1
    endloop
 return 0

This is O(n), a linear search.

Now:

JASS:


...
    private integer n

    //These two are sorted by ascending H
    private integer array H
    private integer array V
    
...

... takes handle h returns integer
local integer top=n+1
local integer bottom=0
local integer half
local integer hi=H2I(h)

    loop
           exitwhen top-bottom==1
           set half=(top-bottom)/2
           if (H[half]>hi) then
                  set top=half
           else
                  set bottom=half
           endif
    endloop
    if (H[bottom]!=hi) then
           return 0 //not found
    endif
 return V[bottom]

This is a binary search, O(log(n))

JASS:

    private integer array V[60000]

... takes handle h returns integer
local integer x=H2I(h)-MIN_HANDLE_INDEX

    return V[x]

This is similar to CSData, data system, etc. It is O(1)