CODEWITHSUNDEEP
javaalgorithmruntime
Lunar
Lunar

Reputation: 4711

Working out program running time?

I am trying to work out the running time of my splitting program,

void splitX(int x) {
     if (x<=1) {return x;};
     splitX(n/2);
     System.out.println("splitting in progress");
     splitX(n/2);
     splitX(n/2);
     splitX(n/2);
}

I am fairly new to this, this is what have done so far;

T(n) = 4T(n/2)
     = 4^2T(n/2^2)
     = 4^3T(n/2^3)
     = 4^kT(n/2^k)
     = O(log n)

Am i on the right track, im getting a little confused, also do you have to account for the printing line?

Upvotes: 1

Views: 185

Answers (4)

pawan
pawan

Reputation: 401

the expression is of form

T(n)=4T(n/2) + c

now apply master theorum using a=4, b=2 and f(n)=c;

T(n)=O(n^loga) //base 2

T(n)=n^2

Upvotes: 0

amit
amit

Reputation: 178521

The analyzis is true until the end, the solution is T(n) = O(n^2)

Note that 4^kT(n/2^k) != O(log n) since 4^k is not a constant.
Have a look at the analyzis:

T(n) = 4T(n/2) = 
     = 4^2T(n/2^2)
     = 4^3T(n/2^3)
     = 4^kT(n/2^k)
     = 4^log(n)*T(1) =
     = 4^log(n) * 1 =
     = (2^log(n))^2 =
     = n^2
     = O(n^2)

To formally prove it: we use induction
base: T(1) = 1 = 1^2
Assume T(n) = n^2 for each k <= n
T(2n) = 4*T(n) =(induction hypothesis) 4*n^2 = (2n)^2

Thus the induction hypothesis is true and T(n) = n^2

You can also check this result on wolfram alpha

Upvotes: 3

mishadoff
mishadoff

Reputation: 10789

Yes, in Big-O notation it's O(log n) mulltiply by constant.

Upvotes: 0

WeaselFox
WeaselFox

Reputation: 7400

As I see it you make log(N) calls to your recursive function. multiplying this by a constant - 4- does not change complexity, nor does the printing line (for all homework related needs).

Upvotes: 0

Related Questions