Cosa significa esattamente O (log n)?

Attualmente sto imparando i tempi di esecuzione di Big O Notation e i tempi ammortizzati. Comprendo la nozione di O (n) tempo lineare, nel senso che la dimensione dell’ingresso influisce proporzionalmente sulla crescita dell’algoritmo … e lo stesso vale, ad esempio, per il tempo quadratico O (n 2 ) ecc. , come i generatori di permutazione, con O (n!) volte, che crescono per fattori.

Ad esempio, la funzione seguente è O (n) perché l’algoritmo cresce in proporzione al suo input n :

f(int n) { int i; for (i = 0; i < n; ++i) printf("%d", i); } 

Allo stesso modo, se ci fosse un ciclo annidato, il tempo sarebbe O (n 2 ).

Ma cosa è esattamente O (log n) ? Ad esempio, cosa vuol dire che l’altezza di un albero binario completo è O (log n) ?

So (forse non in modo molto dettagliato) che cos’è Logarithm, nel senso che: log 10 100 = 2, ma non riesco a capire come identificare una funzione con un tempo logaritmico.

Non riesco a capire come identificare una funzione con un tempo di registro.

Gli attributi più comuni della funzione di runtime logaritmico sono:

  • la scelta dell’elemento successivo su cui eseguire un’azione è una delle varie possibilità, e
  • solo uno dovrà essere scelto.

o

  • gli elementi su cui viene eseguita l’azione sono cifre di n

Questo è il motivo per cui, ad esempio, cercare persone in una rubrica è O (log n). Non è necessario controllare ogni persona nella rubrica per trovare quella giusta; invece, puoi semplicemente dividere e conquistare guardando in base a dove il loro nome è in ordine alfabetico, e in ogni sezione devi solo esplorare un sottoinsieme di ogni sezione prima di trovare il numero di telefono di qualcuno.

Ovviamente, una rubrica più grande ti richiederà ancora più tempo, ma non aumenterà altrettanto rapidamente quanto l’aumento proporzionale delle dimensioni aggiuntive.


Possiamo espandere l’esempio della rubrica per confrontare altri tipi di operazioni e il loro tempo di esecuzione. Assumeremo che la nostra rubrica telefonica contenga aziende (le “Pagine Gialle”) che hanno nomi e persone univoci (le “Pagine Bianche”) che potrebbero non avere nomi univoci. Un numero di telefono è assegnato al massimo a una persona o azienda. Assumeremo anche che ci vuole tempo costante per lanciarsi su una pagina specifica.

Ecco i tempi di esecuzione di alcune operazioni che potremmo eseguire sulla rubrica, dal meglio al peggio:

  • O (1) (best case): data la pagina in cui è indicato il nome di un’azienda e il nome dell’attività, trovare il numero di telefono.

  • O (1) (caso medio): data la pagina in cui si trova il nome di una persona e il suo nome, trova il numero di telefono.

  • O (log n): dato il nome di una persona, trova il numero di telefono selezionando un punto casuale a metà della parte del libro che non hai ancora cercato, quindi verifica se il nome della persona è a quel punto. Quindi ripeti il ​​processo a metà della parte del libro in cui si trova il nome della persona. (Questa è una ricerca binaria per il nome di una persona.)

  • O (n): trova tutte le persone i cui numeri di telefono contengano la cifra “5”.

  • O (n): dato un numero di telefono, trova la persona o l’azienda con quel numero.

  • O (n log n): c’era un problema con l’ufficio della stampante e la nostra rubrica telefonica aveva tutte le pagine inserite in ordine casuale. Correggere l’ordine in modo che sia corretto osservando il nome di ogni pagina e quindi inserendo la pagina nel punto appropriato in una nuova rubrica vuota.

Per gli esempi di seguito, siamo ora presso l’ufficio della stampante. Le rubriche telefoniche sono in attesa di essere spedite per posta a ciascun residente o azienda, e su ogni rubrica telefonica è presente un’etichetta che indica dove deve essere inviata la posta. Ogni persona o azienda riceve una rubrica.

  • O (n log n): Vogliamo personalizzare l’elenco telefonico, quindi troveremo il nome di ogni persona o azienda nella copia designata, quindi cercheremo il nome nel libro e scriveremo una breve nota di ringraziamento per il loro patrocinio .

  • O (n 2 ): si è verificato un errore in ufficio e ogni voce in ciascuna rubrica ha uno “0” in più alla fine del numero di telefono. Prendi un po ‘di bianco e rimuovi ogni zero.

  • O (n · n!): Siamo pronti per caricare le rubriche sul dock di spedizione. Sfortunatamente, il robot che avrebbe dovuto caricare i libri è andato in tilt: sta mettendo i libri sul camion in un ordine casuale! Ancora peggio, carica tutti i libri sul camion, poi controlla se sono nel giusto ordine e, in caso contrario, li scarica e ricomincia. (Questo è il temuto tipo bogo .)

  • O (n n ): correggi il robot in modo che stia caricando le cose correttamente. Il giorno dopo, uno dei tuoi collaboratori ti scherza e collega il robot del caricatore ai sistemi di stampa automatizzati. Ogni volta che il robot carica un libro originale, la stampante di fabbrica esegue una duplicazione di tutte le rubriche! Fortunatamente, i sistemi di rilevamento dei bug del robot sono abbastanza sofisticati da impedire al robot di stampare ancora più copie quando incontra un libro duplicato per il caricamento, ma deve comunque caricare ogni libro originale e duplicato che è stato stampato.

Molte buone risposte sono già state pubblicate su questa domanda, ma credo che ci manchi davvero un’importante, ovvero la risposta illustrata.

Cosa significa dire che l’altezza di un albero binario completo è O (log n)?

Il seguente disegno descrive un albero binario. Nota come ogni livello contiene il doppio del numero di nodes rispetto al livello superiore (quindi binario ):

Albero binario

La ricerca binaria è un esempio con complessità O(log n) . Diciamo che i nodes nel livello inferiore dell’albero nella figura 1 rappresentano elementi in una raccolta ordinata. La ricerca binaria è un algoritmo divide et impera e il disegno mostra come occorreranno (al massimo) 4 confronti per trovare il record che stiamo cercando in questo set di dati di 16 elementi.

Supponiamo di avere invece un set di dati con 32 elementi. Continua il disegno sopra per scoprire che ora avremo bisogno di 5 confronti per trovare quello che stiamo cercando, poiché l’albero è cresciuto solo di un livello più profondo quando abbiamo moltiplicato la quantità di dati. Di conseguenza, la complessità dell’algoritmo può essere descritta come un ordine logaritmico.

Tracciando il log(n) su un foglio di carta semplice, si otterrà un grafico in cui l’aumento della curva decelera con n aumenti:

O (log n)

O(log N) significa fondamentalmente che il tempo sale linearmente mentre il n sale in modo esponenziale. Quindi se impiega 1 secondo per calcolare 10 elementi, ci vorranno 2 secondi per calcolare 100 elementi, 3 secondi per calcolare 1000 elementi e così via.

È O(log n) quando dividiamo e conquistiamo il tipo di algoritmi, ad esempio la ricerca binaria. Un altro esempio è l’ordinamento rapido in cui ogni volta dividiamo l’array in due parti e ogni volta che impiega O(N) per trovare un elemento pivot. Quindi NO(log N)

La spiegazione seguente sta usando il caso di un albero binario completamente bilanciato per aiutarti a capire come otteniamo la complessità del tempo logaritmico.

L’albero binario è un caso in cui un problema di dimensione n è suddiviso in sotto-problema di dimensione n / 2 fino a raggiungere un problema di dimensione 1:

altezza di un albero binario

Ed è così che ottieni O (log n) che è la quantità di lavoro che deve essere fatta nell’albero sopra per raggiungere una soluzione.

Un algoritmo comune con O (log n) complessità temporale è la ricerca binaria la cui relazione ricorsiva è T (n / 2) + O (1), cioè ad ogni livello successivo dell’albero si divide il problema in metà e si fa una quantità costante di lavoro aggiuntivo.

Se avevi una funzione che richiede:

 1 millisecond to complete if you have 2 elements. 2 milliseconds to complete if you have 4 elements. 3 milliseconds to complete if you have 8 elements. 4 milliseconds to complete if you have 16 elements. ... n milliseconds to complete if you have 2**n elements. 

Quindi richiede log 2 (n) tempo. La notazione Big O , in senso lato, significa che la relazione deve essere vera solo per il grande n, e che i fattori costanti e i termini più piccoli possono essere ignorati.

Panoramica

Altri hanno fornito buoni esempi di diagrammi, come i diagrammi ad albero. Non ho visto esempi di codice semplici. Quindi oltre alla mia spiegazione, fornirò alcuni algoritmi con semplici istruzioni di stampa per illustrare la complessità delle diverse categorie di algoritmi.

Innanzitutto, ti consigliamo di avere un’idea generale del Logaritmo, che puoi ottenere da https://en.wikipedia.org/wiki/Logarithm . Le scienze naturali usano e il tronco naturale. I discepoli di ingegneria useranno log_10 (log base 10) e gli informatici useranno log_2 (log base 2) molto, poiché i computer sono basati su binari. A volte vedrai le abbreviazioni di log naturale come ln() , gli ingegneri normalmente lasciano il _10 spento e usano solo log() e log_2 è abbreviato in lg() . Tutti i tipi di logaritmi crescono in modo simile, per questo condividono la stessa categoria di log(n) .

Quando guardi gli esempi di codice qui sotto, ti consiglio di guardare O (1), quindi O (n), quindi O (n ^ 2). Dopo che sei buono con quelli, allora guarda gli altri. Ho incluso esempi chiari e varianti per dimostrare come i cambiamenti sottili possano ancora comportare la stessa categorizzazione.

Puoi pensare a O (1), O (n), O (logn), ecc. Come classi o categorie di crescita. Alcune categorie avranno più tempo da fare rispetto ad altre. Queste categorie ci aiutano a ordinare le prestazioni dell’algoritmo. Alcuni sono cresciuti più velocemente man mano che l’input n cresce. La seguente tabella mostra la crescita numerica. Nella tabella seguente, si consideri log (n) come il limite massimo di log_2.

inserisci la descrizione dell'immagine qui

Esempi di codice semplice di varie categorie Big O:

O (1) – Esempi di tempo costante:

  • Algoritmo 1:

Algorithm 1 stampa ciao una volta e non dipende da n, quindi verrà sempre eseguito in tempo costante, quindi è O(1) .

 print "hello"; 
  • Algoritmo 2:

Algorithm 2 stampa ciao 3 volte, tuttavia non dipende da una dimensione di input. Anche se n cresce, questo algoritmo stamperà sempre solo Ciao 3 volte. Detto questo 3 è una costante, quindi questo algoritmo è anche O(1) .

 print "hello"; print "hello"; print "hello"; 

O (log (n)) – Esempi logaritmici:

  • Algoritmo 3: si comporta come “log_2”

Algorithm 3 mostra un algoritmo eseguito in log_2 (n). Si noti che l’operazione di post del ciclo for moltiplica il valore corrente di i per 2, quindi vado da 1 a 2 a 4 a 8 a 16 a 32 …

 for(int i = 1; i <= n; i = i * 2) print "hello"; 
  • Algoritmo 4 - Funziona come "log_3"

Algorithm 4 dimostra log_3. Nota che vado dall'1 al 3 al 9 al 27 ...

 for(int i = 1; i <= n; i = i * 3) print "hello"; 
  • Algoritmo 5: si comporta come "log_1.02"

L'algoritmo 5 è importante, poiché aiuta a mostrare che finché il numero è maggiore di 1 e il risultato viene moltiplicato ripetutamente su se stesso, si sta osservando un algoritmo logaritmico.

 for(double i = 1; i < n; i = i * 1.02) print "hello"; 

O (n) - Esempi di tempo lineare:

  • Algoritmo 6

Questo algoritmo è semplice, che stampa ciao n volte.

 for(int i = 0; i < n; i++) print "hello"; 
  • Algoritmo 7

Questo algoritmo mostra una variazione, in cui stamperà ciao n / 2 volte. n / 2 = 1/2 * n. Ignoriamo la costante 1/2 e vediamo che questo algoritmo è O (n).

 for(int i = 0; i < n; i = i + 2) print "hello"; 

O (n * log (n)) - nlog (n) Esempi:

  • Algoritmo 8

Pensa a questo come una combinazione di O(log(n)) e O(n) . L'annidamento dei loop for ci aiuta a ottenere l' O(n*log(n))

 for(int i = 0; i < n; i++) for(int j = 1; j < n; j = j * 2) print "hello"; 
  • Algoritmo 9

Algorithm 9 è come l'algoritmo 8, ma ognuno dei loop ha permesso delle variazioni, il risultato finale è O(n*log(n))

 for(int i = 0; i < n; i = i + 2) for(int j = 1; j < n; j = j * 3) print "hello"; 

O (n ^ 2) - n al quadrato Esempi:

  • Algoritmo 10

O(n^2) si ottiene facilmente annidando lo standard per i loop.

 for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) print "hello"; 
  • Algoritmo 11

Come l'algoritmo 10, ma con alcune varianti.

 for(int i = 0; i < n; i++) for(int j = 0; j < n; j = j + 2) print "hello"; 

O (n ^ 3) - n cubi Esempi:

  • Algoritmo 12

Questo è come l'algoritmo 10, ma con 3 cicli invece di 2.

 for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) for(int k = 0; k < n; k++) print "hello"; 
  • Algoritmo 13

Come l'algoritmo 12, ma con alcune varianti che danno ancora O(n^3) .

 for(int i = 0; i < n; i++) for(int j = 0; j < n + 5; j = j + 2) for(int k = 0; k < n; k = k + 3) print "hello"; 

Sommario

Quanto sopra fornisce diversi esempi diretti e variazioni per aiutare a dimostrare quali cambiamenti sottili possono essere introdotti che davvero non cambiano l'analisi. Spero che ti dia abbastanza informazioni.

Il tempo di esecuzione logaritmico ( O(log n) ) significa essenzialmente che il tempo di esecuzione aumenta in proporzione al logaritmo della dimensione di input – ad esempio, se 10 elementi richiedono al massimo una certa quantità di tempo x e 100 elementi richiedono al massimo, diciamo che 2x e 10.000 elementi richiedono al massimo 4x , quindi sembra una complessità temporale O(log n) .

Il logaritmo

Ok proviamo e comprendiamo appieno cosa sia in realtà un logaritmo.

Immagina di avere una corda e l’abbiamo legata a un cavallo. Se la corda è direttamente legata al cavallo, la forza che il cavallo dovrà estrarre (per esempio da un uomo) è direttamente 1.

Ora immagina che la corda sia avvolta attorno a un palo. Il cavallo da scappare ora dovrà tirare molte volte di più. La quantità di volte dipende dalla ruvidità della corda e dalla dimensione del palo, ma supponiamo che moltiplicherà la forza di 10 per il tempo (quando la corda fa una virata completa).

Ora se la corda è in loop una volta, il cavallo dovrà tirare 10 volte più forte. Se l’umano decide di renderlo davvero difficile per il cavallo, può far passare di nuovo la corda intorno a un palo, aumentando la sua forza di altre 10 volte. Un terzo ciclo aumenterà nuovamente la forza di altre 10 volte.

inserisci la descrizione dell'immagine qui

Possiamo vedere che per ogni ciclo, il valore aumenta di 10. Il numero di turni necessari per ottenere qualsiasi numero è chiamato il logaritmo del numero, ovvero abbiamo bisogno di 3 post per moltiplicare la forza di 1000 volte, 6 post per moltiplicare la forza di 1.000.000.

3 è il logaritmo di 1.000 e 6 è il logaritmo di 1.000.000 (base 10).

Quindi cosa significa O (log n) in realtà?

Nel nostro esempio sopra, il nostro ‘tasso di crescita’ è O (log n) . Per ogni ciclo aggiuntivo, la forza che la nostra corda è in grado di gestire è 10 volte maggiore:

 Turns | Max Force 0 | 1 1 | 10 2 | 100 3 | 1000 4 | 10000 n | 10^n 

Ora l’esempio precedente utilizzava la base 10, ma fortunatamente la base del log è insignificante quando parliamo di notazione grande.

Ora immaginiamo che stai provando a indovinare un numero compreso tra 1 e 100.

 Your Friend: Guess my number between 1-100! Your Guess: 50 Your Friend: Lower! Your Guess: 25 Your Friend: Lower! Your Guess: 13 Your Friend: Higher! Your Guess: 19 Your Friend: Higher! Your Friend: 22 Your Guess: Lower! Your Guess: 20 Your Friend: Higher! Your Guess: 21 Your Friend: YOU GOT IT! 

Ora ci sono volute 7 ipotesi per farlo bene. Ma qual è la relazione qui? Qual è la maggior quantità di elementi che puoi indovinare da ogni supposizione aggiuntiva?

 Guesses | Items 1 | 2 2 | 4 3 | 8 4 | 16 5 | 32 6 | 64 7 | 128 10 | 1024 

Usando il grafico, possiamo vedere che se usiamo una ricerca binaria per indovinare un numero compreso tra 1 e 100, ci impiegheranno al massimo 7 tentativi. Se avessimo 128 numeri, potremmo anche indovinare il numero in 7 tentativi ma 129 numeri ci porteranno al massimo 8 tentativi (in relazione ai logaritmi, qui avremmo bisogno di 7 ipotesi per un intervallo di valori di 128, 10 tentativi per un intervallo di valori di 1024 7 è logaritmo di 128, 10 è il logaritmo di 1024 (base 2)).

Si noti che ho messo in grassetto “al massimo”. La notazione grande si riferisce sempre al caso peggiore. Se sei fortunato, puoi indovinare il numero in un tentativo e quindi il caso migliore è O (1), ma questa è un’altra storia.

Possiamo vedere che per ogni ipotesi il nostro set di dati si sta riducendo. Una buona regola empirica per identificare se un algoritmo ha un tempo logaritmico è vedere se il set di dati si restringe di un certo ordine dopo ogni iterazione

Che mi dici di O (n log n)?

Alla fine ti imbatterai in un algoritmo di lineraritmica O (n log (n) . La regola del pollice sopra si applica di nuovo, ma questa volta la funzione logaritmica deve essere eseguita n volte, ad esempio riducendo la dimensione di una lista n volte , che si verifica negli algoritmi come un mergesort.

Puoi facilmente identificare se il tempo dell’algoritmo è n log n. Cerca un loop esterno che itera su un elenco (O (n)). Quindi guarda se c’è un anello interno. Se il ciclo interno sta tagliando / riducendo il set di dati su ciascuna iterazione, quel loop è (O (log n), e quindi l’algoritmo complessivo è = O (n log n) .

Disclaimer: L’esempio del logaritmo funebre è stato preso dall’eccellente libro Delight di Matematician di W.Sawyer .

Puoi pensare a O (log N) intuitivamente dicendo che il tempo è proporzionale al numero di cifre in N.

Se un’operazione esegue un lavoro a tempo costante su ogni cifra o bit di un input, l’intera operazione richiederà tempo proporzionale al numero di cifre o bit nell’input, non alla grandezza dell’ingresso; quindi, O (log N) piuttosto che O (N).

Se un’operazione esegue una serie di decisioni a tempo costante ciascuna delle quali dimezza (riduce di un fattore di 3, 4, 5 ..) la dimensione dell’input da considerare, l’intero richiederà tempo proporzionale per registrare la base 2 (base 3 , base 4, base 5 …) della dimensione N dell’input, anziché essere O (N).

E così via.

Il modo migliore in cui ho sempre dovuto visualizzare mentalmente un algoritmo eseguito in O (log n) è il seguente:

Se aumenti la dimensione del problema di una quantità moltiplicativa (cioè moltiplichi la sua dimensione per 10), il lavoro viene aumentato solo di una quantità additiva.

Applicando questo alla tua domanda dell’albero binario in modo da avere una buona applicazione: se raddoppi il numero di nodes in un albero binario, l’altezza aumenta solo di 1 (una quantità additiva). Se lo raddoppi di nuovo, aumenta comunque di 1 (ovviamente suppongo che rimanga bilanciato e tale). In questo modo, invece di raddoppiare il tuo lavoro quando la dimensione del problema si moltiplica, stai solo facendo un po ‘più di lavoro. Ecco perché gli algoritmi di O (log n) sono fantastici.

Cos’è il registro b (n)?

È il numero di volte in cui è ansible tagliare un registro di lunghezza n ripetutamente in b parti uguali prima di raggiungere una sezione di dimensione 1.

Per prima cosa ti consiglio di leggere il seguente libro;

Algorithms (4th Edition)

Ecco alcune funzioni e le loro complessità attese. I numeri indicano le frequenze di esecuzione delle istruzioni .

Ecco alcune funzioni e le loro complessità attese

Seguendo il grafico della complessità del Big-O anche preso da bigocheatsheet Grafico di complessità del Big-O

Infine una semplice vetrina ci mostra come viene calcolato;

Anatomia delle frequenze di esecuzione delle istruzioni di un programma.

Analizzando il tempo di esecuzione di un programma (esempio).

Analizzando il tempo di esecuzione di un programma

Gli algoritmi di divisione e conquista di solito hanno un componente logn al tempo di esecuzione. Questo deriva dal dimezzamento ripetuto dell’input.

Nel caso della ricerca binaria, ogni iterazione getti via metà dell’input. Va notato che nella notazione Big-O, log è log base 2.

Modifica: Come notato, la base del registro non ha importanza, ma quando si ricava la prestazione Big-O di un algoritmo, il fattore di registro verrà dal dimezzamento, quindi perché lo considero come base 2.

Ma cosa è esattamente O (log n)? Ad esempio, cosa significa affermare che l’altezza di un albero binario completo è O (log n)?

Vorrei riformulare questo come ‘l’altezza di un albero binario completo è log n’. Calcolare l’altezza di un albero binario completo sarebbe O (log n), se stavi attraversando passo dopo passo.

Non riesco a capire come identificare una funzione con un tempo logaritmico.

Il logaritmo è essenzialmente l’inverso dell’esponenziazione. Quindi, se ogni “passaggio” della funzione sta eliminando un fattore di elementi dal set di elementi originale, si tratta di un algoritmo del tempo logaritmico.

Per l’esempio ad albero, si può facilmente vedere che l’abbandono di un livello di nodes riduce un numero esponenziale di elementi mentre si continua il percorso. L’esempio popolare di guardare attraverso una rubrica telefonica ordinata per nome è essenzialmente equivalente a percorrere un albero di ricerca binario (la pagina centrale è l’elemento radice, e puoi dedurre a ogni passaggio se andare a destra oa sinistra).

O(log n) refers to a function (or algorithm, or step in an algorithm) working in an amount of time proportional to the logarithm (usually base 2 in most cases, but not always, and in any event this is insignificant by big-O notation*) of the size of the input.

The logarithmic function is the inverse of the exponential function. Put another way, if your input grows exponentially (rather than linearly, as you would normally consider it), your function grows linearly.

O(log n) running times are very common in any sort of divide-and-conquer application, because you are (ideally) cutting the work in half every time. If in each of the division or conquer steps, you are doing constant time work (or work that is not constant-time, but with time growing more slowly than O(log n) ), then your entire function is O(log n) . It’s fairly common to have each step require linear time on the input instead; this will amount to a total time complexity of O(n log n) .

The running time complexity of binary search is an example of O(log n) . This is because in binary search, you are always ignoring half of your input in each later step by dividing the array in half and only focusing on one half with each step. Each step is constant-time, because in binary search you only need to compare one element with your key in order to figure out what to do next irregardless of how big the array you are considering is at any point. So you do approximately log(n)/log(2) steps.

The running time complexity of merge sort is an example of O(n log n) . This is because you are dividing the array in half with each step, resulting in a total of approximately log(n)/log(2) steps. However, in each step you need to perform merge operations on all elements (whether it’s one merge operation on two sublists of n/2 elements, or two merge operations on four sublists of n/4 elements, is irrelevant because it adds to having to do this for n elements in each step). Thus, the total complexity is O(n log n) .

*Remember that big-O notation, by definition , constants don’t matter. Also by the change of base rule for logarithms, the only difference between logarithms of different bases is a constant factor.

Simply put: At each step of your algorithm you can cut the work in half. (Asymptotically equivalent to third, fourth, …)

It simply means that the time needed for this task grows with log(n) (example : 2s for n = 10, 4s for n = 100, …). Read the Wikipedia articles on Binary Search Algorithm and Big O Notation for more precisions.

If you plot a logarithmic function on a graphical calculator or something similar, you’ll see that it rises really slowly — even more slowly than a linear function.

This is why algorithms with a logarithmic time complexity are highly sought after: even for really big n (let’s say n = 10^8, for example), they perform more than acceptably.

These 2 cases will take O(log n) time

 case 1: f(int n) { int i; for (i = 1; i < n; i=i*2) printf("%d", i); } case 2 : f(int n) { int i; for (i = n; i>=1 ; i=i/2) printf("%d", i); } 

O(log n) is a bit misleading, more precisely it’s O(log 2 n), ie (logarithm with base 2).

The height of a balanced binary tree is O(log 2 n), since every node has two (note the “two” as in log 2 n) child nodes. So, a tree with n nodes has a height of log 2 n.

Another example is binary search, which has a running time of O(log 2 n) because at every step you divide the search space by 2.

But what exactly is O(log n)

What it means precisely is “as n tends towards infinity , the time tends towards a*log(n) where a is a constant scaling factor”.

Or actually, it doesn’t quite mean that; more likely it means something like ” time divided by a*log(n) tends towards 1 “.

“Tends towards” has the usual mathematical meaning from ‘analysis’: for example, that “if you pick any arbitrarily small non-zero constant k , then I can find a corresponding value X such that ((time/(a*log(n))) - 1) is less than k for all values of n greater than X .”


In lay terms, it means that the equation for time may have some other components: eg it may have some constant startup time; but these other components pale towards insignificance for large values of n, and the a*log(n) is the dominating term for large n.

Note that if the equation were, for example …

time(n) = a + b log(n) + c n + d n n

… then this would be O(n squared) because, no matter what the values of the constants a, b, c, and non-zero d, the d*n*n term would always dominate over the others for any sufficiently large value of n.

That’s what bit O notation means: it means “what is the order of dominant term for any sufficiently large n”.

I can add something interesting, that I read in book by Kormen and etc. a long time ago. Now, imagine a problem, where we have to find a solution in a problem space. This problem space should be finite.

Now, if you can prove, that at every iteration of your algorithm you cut off a fraction of this space, that is no less than some limit, this means that your algorithm is running in O(logN) time.

I should point out, that we are talking here about a relative fraction limit, not the absolute one. The binary search is a classical example. At each step we throw away 1/2 of the problem space. But binary search is not the only such example. Suppose, you proved somehow, that at each step you throw away at least 1/128 of problem space. That means, your program is still running at O(logN) time, although significantly slower than the binary search. This is a very good hint in analyzing of recursive algorithms. It often can be proved that at each step the recursion will not use several variants, and this leads to the cutoff of some fraction in problem space.

Albero

log x to base b = y is the inverse of b^y = x

If you have an M-ary tree of depth d and size n, then:

  • traversing the whole tree ~ O(M^d) = O(n)

  • Walking a single path in the tree ~ O(d) = O(log n to base M)

I can give an example for a for loop and maybe once grasped the concept maybe it will be simpler to understand in different contexts.

That means that in the loop the step grows exponentially. Per esempio

 for (i=1; i<=n; i=i*2) {;} 

The complexity in O-notation of this program is O(log(n)). Let's try to loop through it by hand (n being somewhere between 512 and 1023 (excluding 1024):

 step: 1 2 3 4 5 6 7 8 9 10 i: 1 2 4 8 16 32 64 128 256 512 

Although n is somewhere between 512 and 1023, only 10 iterations take place. This is because the step in the loop grows exponentially and thus takes only 10 iterations to reach the termination.

The logarithm of x (to the base of a) is the reverse function of a^x.

It is like saying that logarithm is the inverse of exponential.

Now try to see it that way, if exponential grows very fast then logarithm grows (inversely) very slow.

The difference between O(n) and O(log(n)) is huge, similar to the difference between O(n) and O(a^n) (a being a constant).

In information technology it means that:

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, such that for all N>N0 "C*g(n) > f(n) > 0" is true. 

Ant it seems that this notation was mostly have taken from mathematics.

In this article there is a quote: DE Knuth, “BIG OMICRON AND BIG OMEGA AND BIG THETA”, 1976 :

On the basis of the issues discussed here, I propose that members of SIGACT, and editors of computer science and mathematics journals, adopt notations as defined above, unless a better alternative can be found reasonably soon .

Today is 2016, but we use it still today.


In mathematical analysis it means that:

  lim (f(n)/g(n))=Constant; where n goes to +infinity 

But even in mathematical analysis sometimes this symbol was used in meaning “C*g(n) > f(n) > 0”.

As I know from university the symbol was intoduced by German mathematician Landau (1877-1938)

The complete binary example is O(ln n) because the search looks like this:

 1 2 3 4 5 6 7 8 9 10 11 12 

Searching for 4 yields 3 hits: 6, 3 then 4. And log2 12 = 3, which is a good apporximate to how many hits where needed.

If you are looking for a intuition based answer I would like to put up two interpretations for you.

  1. Imagine a very high hill with a very broad base as well. To reach the top of the hill there are two ways: one is a dedicated pathway going spirally around the hill reaching at the top, the other: small terrace like carvings cut out to provide a staircase. Now if the first way is reaching in linear time O(n), the second one is O(log n).

  2. Imagine an algorithm, which accepts an integer, n as input and completes in time proportional to n then it is O(n) or theta(n) but if it runs in time proportion to the number of digits or the number of bits in the binary representation on number then the algorithm runs in O(log n) or theta(log n) time.

Actually, if you have a list of n elements, and create a binary tree from that list (like in the divide and conquer algorithm), you will keep dividing by 2 until you reach lists of size 1 (the leaves).

At the first step, you divide by 2. You then have 2 lists (2^1), you divide each by 2, so you have 4 lists (2^2), you divide again, you have 8 lists (2^3)and so on until your list size is 1

That gives you the equation :

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(you take the lg of each side, lg being the log base 2)

Every time we write an algorithm or code we try to analyze its asymptotic complexity. It is different from its time complexity .

Asymptotic complexity is the behavior of execution time of an algorithm while the time complexity is the actual execution time. But some people use these terms interchangeably.

Because time complexity depends on various parameters viz.
1. Physical System
2. Programming Language
3. coding Style
4. And much more ……

The actual execution time is not a good measure for analysis.

Instead we take input size as the parameter because whatever the code is, the input is same. So the execution time is a function of input size.

Following is an example of Linear Time Algorithm

Linear Search
Given n input elements, to search an element in the array you need at most ‘n’ comparisons . In other words, no matter what programming language you use, what coding style you prefer, on what system you execute it. In the worst case scenario it requires only n comparisons.The execution time is linearly proportional to the input size.

And its not just search, whatever may be the work (increment, compare or any operation) its a function of input size.

So when you say any algorithm is O(log n) it means the execution time is log times the input size n.

As the input size increases the work done(here the execution time) increases.(Hence proportionality)

  n Work 2 1 units of work 4 2 units of work 8 3 units of work 

See as the input size increased the work done is increased and it is independent of any machine. And if you try to find out the value of units of work It’s actually dependent onto those above specified parameters.It will change according to the systems and all.

I would like to add that the height of the tree is the length of the longest path from the root to a leaf, and that the height of a node is the length of the longest path from that node to a leaf. The path means the number of nodes we encounter while traversing the tree between two nodes. In order to achieve O(log n) time complexity, the tree should be balanced, meaning that the difference of the height between the children of any node should be less than or equal to 1. Therefore, trees do not always guarantee a time complexity O(log n), unless they are balanced. Actually in some cases, the time complexity of searching in a tree can be O(n) in the worst case scenario.

You can take a look at the balance trees such as AVL tree . This one works on balancing the tree while inserting data in order to keep a time complexity of (log n) while searching in the tree.