Når vi diskuterer kjøretid, har vi vanligvis én parameter – problemstørrelsen. Men enkelte ganger, som for grafalgoritmer, så har vi plutselig to parametre. Hvordan skal vi egentlig tolke det?

Kjøretiden til en algoritme beskriver vi gjerne som en funksjon \(T\) som tar inn én parameter \(n\). Dette er ment å beskrive tiden det tar å utføre algoritmen på instanser av størrelse \(n\), der størrelse kan ha litt ulik betydning, avhengig av kontekst, men det dreier seg gjerne om hvor mye plass instansen tar, eller hvor mange elementer den inneholder. Det er naturligvis en fiksjon at algortimen har en fast kjøretid for en gitt \(n\); tiden vil normalt variere med hvilken instans av størrelse \(n\) vi har. Om vi velger én eller annen instans for hver mulig \(n\), så gir det oss én bestemt funksjon \(T\). Vi kan for eksempel for hver \(n\) velge den instansen som maksimerer \(T(n)\), noe vi omtaler som verste tilfelle. Tilsvarende kan vi definere beste tilfelle, eller vi kan definere en funksjon som ikke nødvendigvis beskriver faktiske kjøretider, men en ren forventning over mulige instanser, gitt en sannsynlighetsfordeling.

I noen tilfeller ønsker vi å bruke flere enn én parameter. For eksempel når vi diskuterer grafer, så kan vi beskrive problemstørrelsen ved hjelp av antall noder \(n\) og antall kanter \(m\) (resp. \(|V|\) og \(|E|\)). Når vi da skal vurdere hva som er verste tilfelle eller lignende, så blir det for hver kombinasjon av parametre. Vi låser alle parametre – her \(n\) og \(m\) – og så vurderer vi hva som er verste mulige kjøretid. For eksempel vil bredde-først-søk i en graf med \(n\) noder og \(m\) kanter ha en kjøretid i verste tilfelle på:

\[T(n,m) = \Theta(n + m)\]

Det er med andre ord ikke snakk om å låse en samlet problemstørrelse, og så vurdere hvilken av \(n\) og \(m\) som bør være høyest for å få en høy kjøretid.

Her har jeg også brukt asymptotisk notasjon med flere parametre. Det er dem som argumenterer for at dette er problematisk, men det er en utbredt praksis. Læreboka gir en formell definisjon av \(O\)-notasjon med flere parametre i oppgave 3.2-7, der oppgaven er å gi tilsvarende definisjoner for \(\Omega\) og \(\Theta\). Definisjonen er en likefrem utvidelse, der vi sier at \(f(n,m)=O(g(n,m))\) hvis \(g\) kan skaleres til å ligge over \(f\) for alle høye nok verdier av \(n\) og \(m\). Det vil si, hvis det finnes \(c\), \(n_0\) og \(m_0\) slik at

\[0 \leq f(n,m) \leq cg(n,m)\]

hvis \(n\geq n_0\) eller \(m\geq m_0\). Her, som ellers, må man også anta at \(c\), \(n_0\) og \(m_0\) er positive.