CODEWITHSUNDEEP
ccomplexity-theoryrecurrence
Katherine
Katherine

Reputation: 291

Finding recurrence relation and complexity

Based on the number of operations, finding out the recurrence relation!

a = N;
var = 0;
while (a > 1) 
{
var = var + a; 
num = 2 * var; 
a = a / 2;
}

I think that the the recurrence relaton that will be formed is: (Assignment operations are to be not counted)

T(n)= (from a=1 to N)Σ(3)

Am I right??

Now using this recurrence relation, how to find its complexity.

Upvotes: 1

Views: 100

Answers (3)

Patrick87
Patrick87

Reputation: 28292

The recurrence relation is:

T(1) = a
T(n) = b + T(n/2)

The first part comes from the case where the loop variable equals 1, in which case only the comparison at the top of the loop executes. The second line comes from the constant amount of work done in the loop body, b, plus the time to execute the loop with the updated loop variable value.

The first few terms are:

n   T
1   a
2   a + b
4   a + 2b
8   a + 3b

Based on this we can guess the general form:

T(n) = a + b log n

Proving that is left as an exercise; but you can just plug it in to the recurrence relation to see that it satisfies the requirements.

The asymptotic complexity is logarithmic.

Upvotes: 1

BitTickler
BitTickler

Reputation: 11875

Empirical approach:

First reduce the "educational noise" from the code by simplifying it and add an iteration counter (c). Then look at the result (N,count) and after a while you see, that 2 ^ count = N for all N in [1,2,4,8,16,..].

So the complexity Compl(loop) = O(log_2(N)).

let rec loop a c = 
    match a with
    | x when x > 1 -> 
        let a1 = a / 2
        loop a1 (c+1)
    | _ -> (a,c)

// after staring at the result of the computation we came up with this theory:
let theory n = int (System.Math.Log10(float n) / System.Math.Log10(2.0))

[1..64] 
|> List.map (fun a -> a,loop a 0, theory a) 
|> List.map (fun (a0,(a,c),aa) -> a0,c,aa)

Data:

[(1, 0, 0); (2, 1, 1); (3, 1, 1); (4, 2, 2); (5, 2, 2); (6, 2, 2); (7, 2, 2); (8, 3, 3); (9, 3, 3); (10, 3, 3); (11, 3, 3); (12, 3, 3); (13, 3, 3); (14, 3, 3); (15, 3, 3); (16, 4, 4); (17, 4, 4); (18, 4, 4); (19, 4, 4); (20, 4, 4); (21, 4, 4); (22, 4, 4); (23, 4, 4); (24, 4, 4); (25, 4, 4); (26, 4, 4); (27, 4, 4); (28, 4, 4); (29, 4, 4); (30, 4, 4); (31, 4, 4); (32, 5, 5); (33, 5, 5); (34, 5, 5); (35, 5, 5); (36, 5, 5); (37, 5, 5); (38, 5, 5); (39, 5, 5); (40, 5, 5); (41, 5, 5); (42, 5, 5); (43, 5, 5); (44, 5, 5); (45, 5, 5); (46, 5, 5); (47, 5, 5); (48, 5, 5); (49, 5, 5); (50, 5, 5); (51, 5, 5); (52, 5, 5); (53, 5, 5); (54, 5, 5); (55, 5, 5); (56, 5, 5); (57, 5, 5); (58, 5, 5); (59, 5, 5); (60, 5, 5); (61, 5, 5); (62, 5, 5); (63, 5, 5); (64, 6, 6)]

Upvotes: 1

CIsForCookies
CIsForCookies

Reputation: 12817

What you want to do is find how many times this operation is called, so consider this: after each call a is divided by 2, so if M = N/2 then T(M) = T(N) - 1.

Now, each iteration of this loop divides N again so you get the following:

T(N) = T(N/2) + 1 = ... = k + T(N/(2^k))

The stop condition is this: a>1 so you need to check when N/(2^k) <= 1

N/2^k = 1 -> log (n) = k

So T(N) = log(n) + T(1) = log(n)

This is the answer in 'big O' notation.

Upvotes: 1

Related Questions