Discussion :

[neeoo11]

bonjour,
en étudiant un peu la théorie de la complexité asymptotique, j'arrive pas à faire la différence en O (n) (un grand tau de n) et l'autre O () avec le petit tiré à l'intérieur du O !

merci pour votre aide

[neeoo11]

exemple d'algorithme

pour i = 1 à n faire
pour j = 1 à i faire
x += 3

à votre avis c'est quoi la complexité de cet algo !?

[pseudocode]

bonjour,
en étudiant un peu la théorie de la complexité asymptotique, j'arrive pas à faire la différence en O (n) (un grand tau de n) et l'autre O () avec le petit tiré à l'intérieur du O !

merci pour votre aide

f=O(g) : f est dominée par g (--> le ratio f/g ne tend pas vers l'infini)

f=Ω(g) : f domine g (--> le ratio f/g ne tend pas vers 0)

f=θ(g) : f est équivalente a g (--> le ratio f/g ne tend ni vers 0, ni vers l'infini)