Big O

The concept of Big O could be used to describe the data transferring and mutation runtime.

Time Complexity

In traditional CS Math: Big O (O) - Describes an upper bound on time Big Omega ($\Omega$) - The equivalent concept to O but the lower bound on time Big Theta ($\Theta$) - Both O and $\Omega$ and gives a tight bound on time - this is closer to the actual meaning of what people refer to the Big O

In an interview it’s best to describe a runtime in three parts: Let’s take quick sort for an example: Best case: $O(N)$ - If all the elements are fairly equal in value Worst case: $O(N^{2})$ - If the pivot is repeatedly the biggest element in the array Expected case: $O(N \log{N})$ - Pivot will either be very low or very high

It’s rare to discuss best case because its not very useful in algorithm development.

Big theta or also generally known as Big O describes the best, worst, and expected case of runtime.

Space Complexity

The amount of memory used during an algorithm can also be described with the Big O.

In recursive algorithms recursive calls will add up in space complexity because the space needed in the stack space.

In algorithm that uses call backs, some stacks will have a limit because calls do not exists simultaneously.

Dropping the Constants and Non Dominant Terms

When using Big O in an interview we are using it to describe a rate as input scales. For this reason we drop the constants in runtime. It’s better to describe a general bound like Big Theta, which again describes best, worst, and expected case.

We can also drop non-dominant terms and simplify.

![[Pasted image 20230929101952.png]] Common big O times from slowest to fastest:

Name	Function
Factorial	$O(n!)$
Quadratic	$O(2^{n}$
Linearithmic, Loglinear, Quasilinear	$O(n\log{n})$
Linear	$O(n)$
Fractional Power	$O(n\frac{c}{n})$
Polylogarithmic	$O((\log{n})^{c})$
Logarithmic	$O(\log{n})$
Double Logarithmic	$O(\log{\log{n}})$
Constant	$O(1)$

Amortized Time

Also known as average runtime, can describe the overall performance with the worst case scenario that happens once in a while. To get the amortized time, you can just average the worst case and the expected case.

Log N Run times

If we take Binary Search as an example, we start off with N elements to search, then split the array in half until it becomes one. When dividing N by 2 each time it is likely that it is $O(\log{N})$ .

The base of Log N does not matter as much for big O because of Bases of Logs. Logs of different bases are only off by a constant factor - since we drop the constants we ignore what base of a log within a big O.

Recursive Run times

Given this code:

int f(int n){
	if(n <= 1){
		return 1;
	}
	return f(n-1) + f(n-1);
}

The tree will have depth of n. Each node will have the same amount of children as the function calls. Therefore the next levels will have double the amount of nodes. Which can be expressed as the Sum of Powers of 2. This can be expressed by $2^{n}-1$.

The runtime will often look like $O(branches^{depth})$ or $O(numFuncCalls^{lengthArray})$

For space, although there is $O(2^{n})$ only $O(n)$ exists at a time.

Determining the Big O for Multi-Part Algorithms

If the form of the algorithm is:

Do this, then when you’re all done do that - you add Do this for each time you do that - you multiply

For a more complex algorithm - given this example:

string[][] sort(string[][] array){
	for each el in array            \\ a
		sort each string            \\ O(s log s)
		sort into a full array      \\ O(a log a)    
}

We can define terms as:

• $s$ being the longest string
• $a$ being the length of the array

For each element we sort each string using comparison sort $O(s \log{s})a = O(as \log{s})$ When sorting each string into the full array $O(a \log{a})$ using comparison sort, and inside of each string comparison it will take $O(s)$ there for giving $O(as \log{a})$. We combine these terms with addition because for each iteration they run non dependent of each other. Resulting in $O(2as(\log{a}+\log{s})) \to O(as(\log{a}+\log{s}))$.

** Given a balanced binary tree search

int sum(Node node){
	if (node == null){
		return 0;
	}
	return sum(node.left) + node.value + sum(node.right);
}

The worst case it touches everyone node once, but then the runtime is $O(n)$. Even with the recursive pattern -> O(function calls ^ number of elements) -> $O(2^{\log{n}})$ Using $2^{p}= Q\to \log{2}Q = P$ we can turn $P=2^{\log{n}}$ and this turns $\log{2}P=\log{2}N$

Therefore the runtime is O(N)

Brute force fibonacci solutions are usually $O(2^{n})$ but with memoization (caches) can reduce the runtime by $O(N)$