Time Complexity

  1.  Time complexity vs No. of iterations
    • Time complexity --> how algorithm scales with data (means for very large n)
      • Eg.- N² v/s 1000*n ==> for small n --> N² is better but very negligible difference
      • But for large n ---> huge difference (seconds v/s hours) 
    • Big Oh - supremum    (worst case)
    • Big Omega - infimum     (best case)
    • Big Theta - lies in range [infimum,supremum] => Gives clear picture of time 
      • average case = > O({∑all possible time}/ total number of possibilities)

  2. Amortized / Average time complexity
    • When we insert element into vector using push_back => two scenarios can occur:
      • The array has room for the new element => O(1)
      • The array is full => resized to make room for the new element. 
        This involves creating a new array of 2*size, copying the elements from the old array to the new one, and then adding the new element. This operation has a time complexity of O(n)
    • in C++11 => elements are moved instead of copy
    • For simplicity, let’s take initial capacity as 1
      Insertion 1: costs 1 (array resize from 1 to 2)
      Insertion 2: costs 2 (array resize from 2 to 4)
      Insertion 3: costs 1 (no resize needed)
      Insertion 4: costs 4 (array resize from 4 to 8)
      Insertion 5 to 7: each cost 1 (no resize needed)
      Insertion 8: costs 8 (array resize from 8 to 16)
      And so on…
    • adding all iteration --> ans = (n + ∑ 2^i ==> [ i from 0 log n])
      • effectively ans < 3*n
      • average < 3 --> Time complexity = O(1)
  3. Space complexity = height of (recursion tree) or (state diagram)


Time complexity of recursion tree is (total no. of nodes)*(time per node)
[NOTE : Take total no. of nodes --> Not only leaf nodes]

Questions :

  • void permutation(String str) 
    {
        permutation(str, "");
    }

    void permutation(String str, String prefix) 
    {
        if (str.length() == 0) 
            cout<<prefix;   ----> Takes O(n)
        else 
             for (int i= 0; i < str.length(); i++) 
            {
                String rem = str.substring(0,i) + str.substring(i+1);
                      ----> Takes O(n)
                  permutation(rem, prefix + str.charAt(i));
             }
    }
    • O(n² * n!) => as Work done per node = n*n  --> n for printing & other n for taking out the ith  character
      • Total nodes = n! ---> number of possible permutations

  • void allFib(int n) {
    for (int i= 0; i < n; i++) {
             cout<<(fib (i));
    ---> Time complexity = O(2^n) bcz ∑ 2^i = 2^(n+1)
    Time complexity is NOT  n*2^n  !!!
        }
    }

    int fib(int n) {
        if (n <= 0) return 0;
        else if (n == 1) return 1;
        return fib(n - 1) + fib(n - 2); 
    ---> Time complexity = O(2^n)and Space complexity = O(n)
    }
    • Overall, Time complexity = O(2^n)

  • Code for sqrt of x > 0 upto 8 decimal places l = 0, r = max(1, x), e = 1e-8; ---> Method-1
        while (r - l > e)
        {
            Normal binary search
        } Time complexity = O((log n)*(1/e)) as precision (e) ↑ => elements ↑
    eg.- e = 1 --> 2, 3
               e = 0.1 --> 2.0,  2.1,  2.2,  2.3,  2.4,  2.5, .... , 3.0 
     

    as above took 90 steps => in 150 steps => obviously get better solution

    l = 0, r = max(1, x), steps = 150 ---> Method-2
        while (steps)
        {
            Normal binary search
    steps--
        }

Comments

Post a Comment

Popular posts from this blog

Templates (for CP)

Next smaller element in left and right side of any element -  Link     (Can easily modify) Next greater element for both sides in one pass -  Link String Hashing -  Link MUST call precalc() inside function Count inversions in any random array (GENERAL)  -  Link Count inversions in binary string -  Link Sum of XOR of all subarrays -  Link  ——₪——  Original question link Sum of XOR of all subsequence -   Link  ——₪——  Original question link Prefix sum of 2-D array -  Link Number of subarrays with sum = k →  Link Number of subarrays with sum divisible by k  →  Link Segment Trees →  Link djikstera algorithm -  Link Prime Factorization of given number n →  Link Count no. of divisors in  O(N ⅓ )  →  Link
Read more

DSA Trees + Heap

Image
Trees are special form of graph If n nodes => n-1 edges (means 2 points have only 1 line joining them) They are acyclic => means from node A to node B there is only 1 way to reach Whenever see  stuffs like  connected ,  unique path  -> tree Types of traversal in trees inorder traversion - left -> root -> right preorder traversion - root -> left  -> right postorder traversion - left  -> right -> root If first time visited -> must be root (bcz parent hai)  => PRE-ORDER If second time visited -> left subtree fully analyzed bcz we are moving in anti-clockwise direction => toh left check krke hi aayenge  => IN-ORDER If third time visited -> left and right subtree fully analyzed => POST-ORDER Post-order is reverse of Pre-order from clockwise Binary search tree (BST) = Binary tree + Search property each subtree follows -- left subtree < root value < right subtree Inorder traversal in BST is...
Read more

Modular Basics + Number Theory + Permutations

Image
Binary Exponentiation - to find   a b  →  converted b into binary  Benefit - instead of multiplying b times => multiply   lo g 2 ( b ) times If a is large  →  take  (a % M) If M is itself very large (like 1e18) =>  instead of a*a  →  DO a+a+a....(a times) even if a*a = 1e18  →  will not get reduced log²(n) bcz log(n) for binary_Multiply & log(n) f or expo Same code as expo => Only change * to + everywhere If b is large in a b  →  a b c  ≠  a ( b c  %  M )  ( mod M )  →   cannot take mod in power Use Euler Theorem  →  a b c ≡ a ( b c  % ɸ(m) )  (mod M )  → ɸ is euler totient function For safety, add extra ɸ in power bcz above fails if gcd(a, m) ≠  1 a b c ≡ a (ɸ(m) + ( b c  % ɸ(m) )) ( mod M )   →  updated GCD + prime  properties a divides b + b divides a ---> a =  ±  b gcd is alwa...
Read more