CODEWITHSUNDEEP
ccomplexity-theory
Danny
Danny

Reputation: 45

How to calculate the time complexity of the following function?

The time complexity of the following code is O(2^n), could you please explain to me why?

int f(int n)
{
 if (n == 1)
 return 1;
 return 1 + f(f(n-1));
}

Thanks in advance

Upvotes: 1

Views: 139

Answers (2)

Tarik
Tarik

Reputation: 11209

f(n) = n is a solution for this recurence relation

Proof: f(n) = f(f(n-1)) + 1 = f(n-1) + 1 = (n-1) + 1 = n

Sample VBA code that verifies it:

Sub test()
    For i = 1 To 20
        Debug.Print i, f(i)
    Next
End Sub

Function f(ByVal n As Long) As Long
    If n = 1 Then
        f = 1
    Else
        f = 1 + f(f(n - 1))
    End If
End Function

Since we have established that f(n) = n, we can conclude that

f(n-1) = n-1

Assuming that it takes An calls to get f(n), An being a recurrence relation:

An = 1 + 2 * An-1
  • The call to calculate f(n)
  • The numbers of calls necessary to calculate f(n-1) which will return n-1
  • then the same number of calls to calculate f(f(n-1)) since we are calling f with n-1 again.

The solution of the recurrence relation is 2^n - 1

Upvotes: 1

Tarik
Tarik

Reputation: 11209

Cost complexity is 2^n -1

VBA Code:

Option Explicit Dim count As Long

Sub test()
    Dim i As Integer
    For i = 1 To 20
        count = 0
        f i
        Debug.Print i, count
    Next
End Sub

Function f(ByVal n As Long) As Long
    count = count + 1
    If n = 1 Then
        f = 1
    Else
        f = 1 + f(f(n - 1))
    End If
End Function

Output:

1   1
2   3
3   7
4   15
5   31
6   63
7   127
8   255
9   511
10  1023
11  2047
12  4095
13  8191
14  16383
15  32767
16  65535
17  131071
18  262143
19  524287
20  1048575

Upvotes: 0

Related Questions