# Tag Info

### Do edge lists have O(E) storage if default values are used for absent keys?

Just as an initial comment, it's not entirely settled what Bachmann big-oh notation formally means when you have more than one variable. There are multiple competing definitions. But let's leave that ...
• 22.3k

### Diffucuty in understanding code after a recursive call

You use complete induction and prove two things: 1. The function is correct for the starting case (often i = 0 or i = 1). 2. If the function is correct for all cases with i < I, then it is also ...
• 30.7k

### When do we multiply or add the time complexities of loops?

There is no simple rule with O(f(n)). If loop 1 takes $\Theta(f(n))$ and loop 2 which is run once for every iteration of loop 1 takes $\Theta(g(n))$, then the total is $\Theta(f(n) \cdot g(n))$. The ...
• 30.7k
Accepted

### When do we multiply or add the time complexities of loops?

Big-O is about worst-case, this means you can typically focus on a simplified version of the function you've got. For worst-case, you need the consider the case where the early returns is not taken, ...
• 540

### When do we multiply or add the time complexities of loops?

Here's the gist of it, but you should try to make it more formal on your own. Ignore, for now the "if bla bla, return True" part. Notice that essentially any time anything interesting ...
• 16.7k
Accepted

### Improve performances of Gauss-Jordan (XOR-SAT) Algorithm?

Thanks to D.W.'s comment, I discovered galois and now have a much better understanding of what the Gauss-Jordan elimination, specifically galois.GF2(m).row_reduce(),...
• 245
1 vote

### Using XOR operation, a MOD operation compute a function f(n)

As we want to use both operations, we only have two possible combinations: $$\left(n \oplus x\right) \mod s\tag{1}\label{1}$$ $$\left(n \mod x\right) \oplus s\tag{2}$$ If we store $f\left(n\right)$ in ...
• 111

Top 50 recent answers are included