Scribd Logo
Upload

Welcome to Scribd!

  • 0 views

    Problems_week_3_Compexity

    Uploaded by

    Dan

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Problems_week_3_Compexity

    Uploaded by

    Dan
    0 views9 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    0 views9 pages

    Problems_week_3_Compexity

    Uploaded by

    Dan

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 9

    1.

    Considerati instructiunile de mai jos si descrieti continutul fiecarei variablile la executia


    acestora cand n are valoarea 3
    Consider the instructions below, describe the content of each variable while
    executing the program when n is 3.

    x <- n
    for k <- 0 to n-1 do
    j <- 0
    while j <= k do
    x <- x + x
    j <- j + 1

    n=3

    We will create a table, who will volunteer?

    Step Instruction Memory

    1 x=3 x=3

    2 k=0 x=3, k = 0

    3 j=0 x=3, k=0, j=0

    4
    2. Sa se determine numărul de operații efectuate de către un algoritm care determina
    numărul ​de inversiuni ale unei permutări.
    Determine the number of operations performed by an algorithm that determines the
    number of inversions of a permutation.

    Pentru o permutare (a1, . . . , an), a.i. i∈ {1, . . . , n}, i = 1, n o inversiune este o pereche de indici (i,
    j) cu proprietatea ca i < j si a​i​ > a​j​ .

    For a permutation (a1, . . . , an), a.i. i∈ {1, . . . , n}, i = 1, n; an inversion is a pair of indices (i,j)
    with the property that i<j and a​i​ > a​j​ .

    procedure inverse(a[1,..,n], n):


    1 k=0
    2 for i = 1; i < = n-1; i++ do
    3 for j = i + 1 ; j <= n ; j++ do
    4 if a[i] > a[j] then
    5 k=k+1
    6 return k
    end

    Index Cost Numar executii

    1 1 1

    2 2*n 1

    3 2*(n-i+1) i=1,n-1

    4 1 i=1,n-1; j = i+1,n

    5 T i=1,n-1; j = i+1,n
    3. Precizati si demonstrati complexitatea timp a următorului algoritm.
    Determine and specify the time complexity of the following algorithm:

    1 sum <- 0
    2 for i <- 0 to n-1 do
    3 for j <- i to n-1 do
    4 for k <- 0 to 4 do
    5 sum <- sum + 2

    Index Cost Repetitions

    1 1 1

    2 2(n+1) 1

    3 2(n-i+1) i=0,n-1

    4 2*5 i=0,n-1, j=i,n-1

    5 1 i=0,n-1, j=i,n-1, k=0,4

    SUM​n-1​i=0​ is a sum from i=0 till n-1

    T(n) = 1 + 2 * ( n + 1 ) + 2*SUM​n-1​i=0​(n-i+1) + 2*SUM​n-1​i=0 ​SUM​n-1​j=i​(5) +SUM​n-1​i=0 ​SUM​n-1​j=i​SUM​4​k=0​(1)

    After this we need to calculate...


    4. Sa se determine termenul dominant si ordinul de crestere pentru expresiile:
    Determine the dominant term and the growth order for the expressions:

    ● T(n)=2lgn + 4n + 3nlgn
    The dominant term in 2lgn + 4n + 3nlgn is 3nlgn and the growth order is n log n.
    ● 2 + 4 + 6 + . . . 2n - is it 2n?

    Dominant term of the sum 2 + 4 + 6 + . . . 2n is not 2n but n^2

    2(1+2+..+n) = 2(n(n+1))/2 = n^2 + n

    Dominant term is n^2 and the growth order is n^2.


    5. Prove that: n! ∈ O(n​n​)
    n! < = n ^ n

    Deci, in limbaj natural, sa se demonstreze ca n! este MARGINIT SUPERIOR de n^n.

    In natural language we must prove that n! is bounded by n^n, n^n is an upper bound.

    Do not forget O is the notation that means: “worse case scenario of an algorithm”

    We must demonstrate that n! < = n ^ n

    -----------------------------------------------Base case--------------------------------
    P(1) : 1! < = 1 ^ 1 ? Yes
    P(2): 2! < = 2 ^ 2 ? 2 < = 4 ? Yes
    ---------------------------------------------------------------------------------------------
    -----------------------------------------------Induction step---------------------------
    P(3): Say that: 3! = 3 * 2! write (k + 1) ! = ( k + 1 ) * P(k) - current step * last step

    3 * P(2) < = 3 ^ 3 ( Yes, 6 < = 27 )


    .
    .
    .
    Suppose that P(k) is true, which means k! < = k ^ k and we will prove P(k+1)

    Prove P(k+1) is true:

    P(k+1): (k+1)! = (k + 1) *​ (k) * (k-1) … (3)*(2)*(1)


    = (k + 1) * ​k! “-​ P(k)”
    ⇒ using the upper supposition that ( k! < = k ^ k )

    It will result that (k+1) * k! <= (k+1)* k ^ k

    Knowing that k < k +1 din (k+1) * k! < (k+1)* k ^ k it will result that

    (k+1) * k! <= (k+1)* k ^ k <= (k+1)(k+1)^k


    = (k+1)^(k+1)
    ---------------------------------------------------------------------------------------------
    or calculate

    lim n!/n^n
    n-> infinity

    limita e 0, daca stam sa calculam, asta inseamna ca n! creste mai greu decat n^n => n^n il
    margineste superior => am demonstrat

    limit is 0 if we calculate, that means that n! grows slower than n^n hence it is a superior bound,
    hence we proved.

    You might also like