Skip to main content

New answers tagged

3 votes

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 ...
Pseudonym's user avatar
  • 22.3k
0 votes

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 ...
gnasher729's user avatar
  • 30.7k
0 votes

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 ...
gnasher729's user avatar
  • 30.7k
-2 votes
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, ...
Matthieu M.'s user avatar
2 votes

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 ...
Pål GD's user avatar
  • 16.7k
0 votes
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(),...
nowox's user avatar
  • 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 ...
Nerrit's user avatar
  • 111

Top 50 recent answers are included