Algorithm Time Complexity

Question

Which of the following describes growth of f(x)?

1. Quadratic

2.Linear

3.Exponential

4.Logarithm

Answer 1

It is exponential only.

recurrence functions will look like

f(n) = f(n-1) + g(n)

g(n) = f(n-1) + g(n/2)

When you are calling f(n), if you will draw a tree it will be at least n level tree on left most and  (log n) level tree on right most. 

if you want to take upper bound then take the maximum level possible and assume the tree to be complete binary tree in worst case so this way, there will be O(2^n) function call. In each fn call takes constant time so time complexity will be O(2^n) i.e exponential.

 

Comments

Thanks Sandeep for the nice explanation. :)

Answer 2

f(x)=f(x-1)+g(x) -----------(i)

g(x)=f(x-1)+g(x/2)-----------(ii)

sub (ii) in (i) we get equation in terms of f(x)

f(x)=f(x-1)+f(x-1)+g(x/2)

=2f(x-1)+g(x/2).

g(x) is growing exponentially (approx)

g(1)=1,g(2)=3,g(3)=6,g(4)=14,g(5)=28,g(6)=56,118,216....its growth is approx exponentially.

f(x)=2*f(x-1)+$2^{n/2}$

=2[2f(x-2)+$2^{(n-1)/2}$]+$2^{n/2}$

=$2^{2}$f(x-2)+$2^{1/2}*2^{n/2}$+$2^{n/2}$

=..

.

=$2^{k}f(n-k)+2^{n/2}[2^{0/2}+2^{1/2}+2^{2/2}+.....2^{(k-1)/2}.]$

take n-k=1 and k=n-1 sub in the above equation.

=$2^{n-1}.1+2^{n/2}[0+2^{1/2}+2^{2/2}+....2^{n/2}]$   (Approx)

=$2^{n-1}+2^{n}*1.3$

=$2^{n}*[1.8]$ 

Hence Growth of f(x) should be exponential

Comments

My approach is as follow :-

Draw tree for f(x),say f(5),it will approximate to complete binary tree so it is asymopotically 2^n ,hence exponential.

Please let me know if u understand this and if this is correct approach?