Big O

Big O time is the language and metric we use to describe the efficiency of the algorithms.

If your algorithm is in the form of "do this, when you're all done, do that" then you add the runtimes.
If your algorithm is in the form of "do this for each time you do that" then you multiply the runtimes.

Add the Runtimes: O(A + B) Multipy the Runtimes: O(A * B)

Add the Runtimes: O(A + B)	Multipy the Runtimes: O(A * B)
`foreach(int a in arrayA) { Console.WriteLine(a); } foreach(int b in arrayB) { Console.WriteLine(b); }`	`foreach(int a in arrayA) { foreach(int b in arrayB) { Console.WriteLine(a + ", " + b); } }`

foreach(int a in arrayA)
{
    Console.WriteLine(a);
}

foreach(int b in arrayB)
{
    Console.WriteLine(b);
}

foreach(int a in arrayA)
{
    foreach(int b in arrayB)
    {
        Console.WriteLine(a + ", " + b);
    }
}

O(n!) < O(2^n) < O(n^2) < O(n log n) < O(n) < O(log n) < O(1)

Asymptotic Notations

Big-Oh

f(x) = O(g(x))

g(x) is an asymptotic upper bound for f(x)

Omega

f(x) = Ω(g(x))

g(x) is an asymptotic lower bound for f(x)

Theta

f(x) = θ(g(x))

g(x) is an asymptotic tight bound for f(x)

Small-o

f(x) = o(g(x))

g(x) is an asymptotic tight upper bound for f(x)

Small-omega

f(x) = ω(g(x))

g(x) is an asymptotic tight lower bound for f(x)

Last updated 1 year ago