let us say I have a recursive call for linked list: ( Singular )
def append(self, val):
def append_rec(node, val):
if node.next is None:
node.next = Node(val)
else:
append_rec(node.next, val)
if self.head is None:
self.head = Node(val)
self.len = 1
else:
append_rec(self.head, val)
self.len = 1
what is the time complexity of a recursive linked list altogether? I am at a little of problem of knowing how to find time complexity. Please explain to me, thanks.
CodePudding user response:
The number of calls of append_rec
corresponds to the number of nodes that are already in the list.
All other steps in this code can be considered O(1) operations, so the total time complexity is linear to the number of nodes already in the list, i.e. O(n).
It may help to visualise the process. Let's say we already have a list with 2 nodes with values 1 and 2:
self
↓
┌─────────┐ ┌────────────┐ ┌────────────┐
│ head: ─────►│ val: 1 │ │ val: 2 │
│ len: 2 │ │ next: ────────►│ next: None │
└─────────┘ └────────────┘ └────────────┘
Now let's say we call the method append
with value 3, then first we get into the else
block of append
where append_rec(self.head, val)
is called. Inside append_rec
we have node
referencing the first node now:
self node
↓ ↓
┌─────────┐ ┌────────────┐ ┌────────────┐
│ head: ─────►│ val: 1 │ │ val: 2 │
│ len: 2 │ │ next: ────────►│ next: None │
└─────────┘ └────────────┘ └────────────┘
The next action is a call of append_rec(node.next, val)
. So now we have a second execution of append_rec
, where also a node
name exists. Let's give it an accent to distinguish it:
self node node'
↓ ↓ ↓
┌─────────┐ ┌────────────┐ ┌────────────┐
│ head: ─────►│ val: 1 │ │ val: 2 │
│ len: 2 │ │ next: ────────►│ next: None │
└─────────┘ └────────────┘ └────────────┘
In this second execution of append_rec
, there is no further recursive call made. Instead a node is created and the tail node's next
attribute gets a reference to it:
self node node'
↓ ↓ ↓
┌─────────┐ ┌────────────┐ ┌────────────┐ ┌────────────┐
│ head: ─────►│ val: 1 │ │ val: 2 │ │ val: 3 │
│ len: 2 │ │ next: ────────►│ next: ────────►│ next: None │
└─────────┘ └────────────┘ └────────────┘ └────────────┘
Once this is done, the second execution instance of append_rec
returns, and the first execution instance has nothing more to do, so it also returns. And finally the append
execution updates the len
attribute and returns too.
self
↓
┌─────────┐ ┌────────────┐ ┌────────────┐ ┌────────────┐
│ head: ─────►│ val: 1 │ │ val: 2 │ │ val: 3 │
│ len: 3 │ │ next: ────────►│ next: ────────►│ next: None │
└─────────┘ └────────────┘ └────────────┘ └────────────┘
I hope this illustrates how append_rec
is called as many times as there are nodes in the list, and how the other actions have a constant time complexity.