i got these methods and i need the overall complexity for them

addEdge() complexity: O(1) BFS() complexity: O(V+E) sendFlow() complexity: O(VE) DinicMaxFlow() complexity: O(V^2E)

overall complexity:

___________________________________ the code _____________________________________________

import time #________________________Dinic's Algorithm---->(adj,graph,queue,array)______________________ # list and a class. The list is used to store the adjacency list of the graph, and the class is used to store information about each edge in the graph. # a queue and an array. The queue is used to store the nodes that need to be visited, while the array is used to store the level of each node.

class Edge: def __init__(self, v, flow, C, rev): self.v = v #o(1) self.flow = flow #o(1) self.C = C #o(1) self.rev = rev #o(1) # class Edge : o(1)

class Graph: def __init__(self, V): self.adj = [[] for i in range(V)] #o(V) self.V = V #o(1) self.level = [0 for i in range(V)] #o(V) def addEdge(self, u, v, C): a = Edge(v, 0, C, len(self.adj[v])) #o(1) b = Edge(u, 0, 0, len(self.adj[u])) #o(1) self.adj[u].append(a) #o(1) self.adj[v].append(b) #o(1) # addEdge function : o(1)

def BFS(self, s, t): for i in range(self.V): #o(V) self.level[i] = -1 self.level[s] = 0 q = [] #o(1) q.append(s) #o(1) while q: #o(V) u = q.pop(0) #o(1) for i in range(len(self.adj[u])): #o(E) e = self.adj[u][i] if self.level[e.v] < 0 and e.flow < e.C: #o(1)

self.level[e.v] = self.level[u]+1 #o(1) q.append(e.v) #o(1)

return False if self.level[t] < 0 else True #BFS function: o(V+E) def sendFlow(self, u, flow, t, start):

if u == t: #o(1) return flow while start[u] < len(self.adj[u]): #o(E) e = self.adj[u][start[u]] if self.level[e.v] == self.level[u]+1 and e.flow < e.C: #o(1)

curr_flow = min(flow, e.C-e.flow) #o(1) temp_flow = self.sendFlow(e.v, curr_flow, t, start) #o(V+E) if temp_flow and temp_flow > 0: #o(1)

e.flow += temp_flow #o(1) self.adj[e.v][e.rev].flow -= temp_flow #o(1) return temp_flow #o(1) start[u] += 1 #o(1) #sendFlow function: #o(VE) def DinicMaxflow(self, s, t):

if s == t: return -1

total = 0

while self.BFS(s, t) == True: #o(V^2E)

start = [0 for i in range(self.V+1)] while True: flow = self.sendFlow(s, float('inf'), t, start) #o(VE^2) if not flow: break total += flow return total #O(1) #DinicMaxflow function: o(V^2E) g = Graph(5000)

def loadGraph(): my_file = open(r"C:\Users\azhar\OneDrive\Documents\algorithms\project\datat.txt", "r") for number in my_file: nums=number.split("\t") row=int(nums[0])-1 col=int(nums[1].strip())-1 g.addEdge(row, col, float(nums[2].strip())) #o(E) loadGraph() start3 = time.perf_counter() f = g.DinicMaxflow(0, 90) #o(V^2E) print("Maximum flow: ", f)#o(1) end3 = time.perf_counter() #o(1) print("time: ",end3 - start3) # o(1)

________________________________________________________________________________