CPP

Time complexity

Trivial Runtime Analysis
**************************************

If there is no input, then it’s called a constant time algorithm. For example:

for (int i = 0; i < 1000000; i ++)
      x++;

above is O(1)
------------------------------------------------------------------------------
Let’s go through some code samples and analyze their runtime complexity.

for (int i = 0; i < N; i ++)
      x++;
All we need to do is count the number of times the statement x++ will execute.
Clearly, it’s N, so the time complexity is O(N), also called linear.
------------------------------------------------------------------------------
for (int i = 0; i < N; i++) 
    for (int j = 0; j < i; j++) 
        x++;
How many times the statement x++ executes:
So the time complexity is O(N^2), also called quadratic.
---------------------------------------------------------------------------

Logarithmic Runtime
**************************************************

Iterating powers of a number #
Let’s analyze the loop below where we iterate over all powers of 2
for (int i = 1; i <= N; i *= 2)
    x++;
    
In Big-O notation, the time complexity is O(logN)

A similar analysis gives O(logN) runtime for the loop below.
for (int i = N; i >= 1; i /= 2)
      x++;
---------------------------------------------------------------------------
Harmonic series #
Consider the piece of code below:

for (int i = 1; i <= N; i++)
    for (int j = i; j <= N; j += i)
        x++;

Therefore, the time complexity is O(NlogN).
---------------------------------------------------------------------------

Non Trivial Runtime
********************************************************

Sum of powers #
Take the code sample below:

for (int i = 1; i <= N; i *= 2)
    for (int j = 1; j <= i; j++)
        x++;
So, the run-time complexity is actually linear - O(N)
-----------------------------------------------------------------------------

Amortized Analysis
*****************************************************************

Consider this algorithm: We start with an array of size 2 
and each operation adds one element to the array, we do this operation N times. 
If the array is full, we see the current size of array say sz. 

Adding to the array if it’s not empty: O(1)
Copying array of size sz to a new location: O(sz)

Total number of operations:

1 + 1 + (1 + 2) + 1 + (1 + 4) + 1 + 1 + 1 + (1 + 8) + 1 + 1…

=> (1 + 1 + ... + 1) N times + (2 + 4 + 8 + ... ) < N + 2N<=3N

So, the complete algorithm runs in O(N) time
Allocate the 2*sz memory and copy the array to its location so we have space for the new sz elements.

time complexity definition

Time complexity is the amount of time taken by an algorithm to run, as a function of the length of the input. It measures the time taken to execute each statement of code in an algorithm.

Time complexity

Recursion Tree Method
(To solve recurrence and get time complexity of recursive function)

1)We write non-recursive part as root of tree and recursive part as it's children.
Then take sum of nodes in each level & find Sum of these sums of each level 
generally terms of thi new Sum will be in ap,gp etc with number of terms as height of tree.
Note : if recursive part is T(n/2) then height of tree is log(n)
if it's T(n-1) then height is n.

2)We keep on expanding Children untill we reach the base case ( aka leaves ).

T(n) = 2T(n-1) + cn
T(1) = c
Where cn is non recursive part.

Note : instead of 0(1) we write constant c, for 0(n) we write cn 
Keep c same everywhere.