Complexity of pmetis and kmetis algorithms

Hi,

What is the complexity of kmetis and pmetis algorithms used for graph partitioning ?

Thanks,
Anjali

RE: The complexity of kmetis is

The complexity of kmetis is approximately O(n + m + klog(k)) where n is the number of nodes, m the number of edges, and k the number of partitions.
The complexity of pmetis is O((n+m)*log(k)).