In my course of algorithms we talk about time complexity with Big O Notation. And I am always confused when I try to calculate the Big O. I know for example when a function then it can be O(n) or O(n²). But I don't know the logical background and how to get this solution for each function.  int func1(int n){     for (int i=1; i&lt;n; i=i*2)     printf("i = %d", i); return i;  }  int func2(int a, int b) {    int result=1;     while (b&gt;0) {       result = result*a;        b = b-1;     }    return result; }  void func3(int n) {    for (int i=0; i&lt;pow(2,n); i++)        printf("%d", i);   }
304
Most people with a degree in CS will certainly know what . It helps us to measure how well an algorithm scales.   But I'm curious, how do you calculate or approximate the complexity of your algorithms?
116458
Find the number of all bijective functions from A to A. Given set A   has n elements   First number of one-to-one functions from A to A is n! as first element has choice of n elements, but second element has only n-1 since by definition of one-to-one it can't go to the first element choice..... Now with onto functions I am stuck how to do .  I notice this question has been answered previously by induction, I just think a counting proof would be more helpful for me to learn. Also I am unable to follow that argument there.
99405
I'm writing a code in C that returns the number of times a non negative integer can be expressed as sums of perfect squares of two non negative integers.  R(n) is the number of couples (x,y) such that x² + y² = n where x, y, n are all  non negative integers.   How can I mathematically compute R(n)?  What is a very fast algorithm I can use to compute R(n)?
48274
What is the Big-O time complexity of the following nested loops: for (int i = 0; i &lt; N; i++) {     for (int j = i + 1; j &lt; N; j++) {         System.out.println(&quot;i = &quot; + i + &quot; j = &quot; + j);     } }  Would it be O(N^2) still?
57700
Why sum of two little "o" notation is equal little "o" notation from sum?  $o( f(n) ) + o( g(n) ) = o( f(n) + g(n) ) ?$  For example:   $f(n) = n^3$  $g(n) = 1/n$   so    $o(f(n)) = n^2$  $o(g(n)) = 1/n^2$   and    $o( f(n) ) + o( g(n) ) = n^2 + 1/n^2$ $o( f(n) + g(n) ) = n^2$   Of course, I could write it like   $o( f(n) ) + o( g(n) ) = n^2 + o( g(n) )$ $o( f(n) + g(n) ) = n^2 + o( g(n) )$   My question is why? I don't understand it, because in first we always get two parameters.
48763
I got this from "4.4 The recursion-tree method for solving recurrences" in book "Introduction to Algorithms"  The recurrence that try to use recursion-tree to solve is: $T(n) = 3T(n/4) + cn^2$
24115
Is there a way to write OO-like code in the C programming language?    See also:       Found by searching on "[c] oo".
34612
Numbers of ways of representing a nonnegative integer as the ordered sum of odd numbers. For the first numbers we find that:  $0 \to 0\quad \text{ways}$  $1 \to 1\quad \text{way}$  $2: (1,1) \to 1\quad \text{ways}$  $3: (1,1,1), (3) \to 2\quad \text{ways}$  $4: (1,1,1,1), (3,1), (1,3)\to 3\quad \text{ways}$  $5: (1,1,1,1,1), (3,1,1), (1,3,1), (1,1,3), (5)\to 5\quad \text{ways}$  So, if $A_n$ is the numbers of ways to represent the nonnegative integer n as the ordered sum of $n$ (nonnegative) odd numbers, then $A_n = F_n$ where $F_n$ is the Fibonacci number.  How could this be proved?   I was trying to prove this by induction, but I'm having problems with the induction step. I really don't know what to do there.
34010
$$T(n) = \sqrt{n} T \left(\sqrt n \right) + n$$  Master method does not apply here. Recursion tree goes a long way. Iteration method would be preferable.  The answer is $Θ (n \log \log n)$.  Can anyone arrive at the solution.
15843
Given the definition of Big-O, prove that $f(n) = n^2 - n$ is $O(n^2)$.  When I use the given definition, I get $n^2 - n \leq n^2 - n^2$ which means that $n^2 -n \leq 0$, which is not true. Is there some step I'm missing?
63673
Apparently recurrences like this cannot be solved with the Master Theorem:  $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$  Because $n^{\log_b(a)} = n^1$ is not a polynomial multiple of $f(n) = \frac{n}{\log(n)}$ since $\frac{n}{\frac{n}{\log(n)}} = \log(n)$, which is less than $n^\epsilon$ for any positive $\epsilon$.  But when is this really even an issue?   For example why wouldn't the time complexity be $n \log n$ using case 2 of the Master Theorem? Unrolling the recursion:  $$T(n) = n\sum_{k=1}^{\log_2(n)} \frac{1}{\log_2(2^k)}$$  $$T(n) = n\sum_{k=1}^{\log_2(n)} \frac{1}{k}$$  Doesn't this suggest $\Theta(n \log n)$ even though it supposedly cannot be done with Master Theorem?
34769
These are all from Sipser's book, second edition. I was just hoping someone could verify/explain those that are more difficult for me.  $2n = O(n)$: true  $n^2 = O(n)$: false  $n^2 = O(n\log^2 n)$: I say false, because $\log^2 n$ grows more slowly than $n$  $n\log n = O(n^2$): true because $n$ grows more quickly than $\log^2n$  $3^n = 2^{O(n)}$: I wasn't sure what this notation meant. Any clarification here?  $2^{2^n} = O(2^{2^n})$: I would say true, but I'm not entirely sure why.  $n = o(2n)$: false, because $o(2n) = o(n)$ and $n$ grows as quickly as itself.  $2n = o(n^2)$: true, $n^2$ is always more than $2n$ for some constant.  $2^n = o(3^n)$: true  $1 = o(n)$: I'm not really sure.  $n = o(\log n)$: false, $n$ is always larger.  $1 = o(1/n)$: true, because 1 is always larger.
94859
Let $x = (x_1, x_2,...,x_n)\in\{0,1\}^n$ for $n\in\mathbb{N}$. Prove that if one-way functions (OWFs) exist, then there exists a one-way function $f$ such that for every bit $i\in[1,n]$ there exists an algorithm $A_i$ such that: $$\Pr[A_i(f(x)) = x_i] \geq \frac{1}{2} + \frac{1}{2n}$$ I'm having trouble understanding this.
54539
Let   $$f(n)=\sum_{x=1}^n\log(x)$$  What is $O(f(n))$?  I know how to deal with sums of powers of $x$. But how to solve for a sum of logs?
79550
Whilst I understand how the RSA algorithm works, I don't understand how the CPU operates when it needs to use the mod function with a huge number $n$, for example.  $n = 8192$ bits; $c = m^e \mod n$;  In essence my question is how does the CPU deal with this huge modulus?
90632
I'm interested in algorithms to quickly compute the inverse factorial. I've noted that large factorials have a unique number of digits. How can I use this fact to quickly compute the factorial? Is there a formula,  n = f(n!) = #digits( (n!) )?  I'm mostly interested in the case where we know our input is correct. But, error checking for values that are not factorials would be a bonus. (Perhaps, someone has thought of a way to do the inverse gamma function quickly?)  I'm interested in inputs that have over a million digits, so simply dividing 1,2,3,...,n will not work.
25054
Problem Statement: We are given a $2-1$ function $f:\{0,1\}^{n}\to\{0,1\}^{n}$ such that: there is a secret string $s\in\{0,1\}^{n}$ such that: $f(x)=f(x\oplus s)$. Challenge: find $s$.     Simon's algorithm says:         Set up a random superposition $$\frac{1}{\sqrt{2}}|r\rangle + \frac{1}{\sqrt{2}}|r\oplus s\rangle$$   Fourier sample to get a random $y$: $$y.s=0\ (\text{mod 2})$$   Repeat steps $n-1$ times to generate $n-1$ linear equations in $s$.         Solve for $s$.   I don't understand steps (1) and (2). Why and how exactly do we set up the random superposition? How does it help? Also, in step (2), what does the dot operator (in $y.s$) stand for? Bit-wise multiplication?