CODEWITHSUNDEEP
algorithmcomplexity-theory
SkyWalker
SkyWalker

Reputation: 14317

big O complexity O(n log n) vs O(n log m)

I have an algorithm that takes a DAG graph that has n nodes and for every node, it does a binary search on its adjacency nodes. To the best of my knowledge, this would be a O(n log n) algorithm however since the n inside the log corresponds only to the adjacency of a node I was wondering if this would become rather O(n log m). By m I mean the m nodes adjacent to each node (which would intuitively and often be much less than n).

Why not O(n log m)? I would say O(n log m) doesn't make sense because m is not technically a size of the input, n is. Besides, worst-case scenario the m can be n since a node could easily be connected to all others. Correct?

Upvotes: 0

Views: 2025

Answers (4)

Yarneo
Yarneo

Reputation: 3012

It is correct that in the worst case of a graph, each node has n-1 neighbours, meaning that it is connected to everyone else, but if that was so for every node then it wont be an acyclic graph. Therefore the average neighbours of each node is less than n.

The maximum number of edges in a DAG is: (n-1)n/2

If we look at each node, it will have an average of (n-1)/2 neighbours. So your complexity would still remain O(n log n) in the worst case.

Upvotes: 0

mcdowella
mcdowella

Reputation: 19621

There are certainly DAGs where one node is connected to every other node. Another example would be a DAG with nodes number 0,1,2...n, where every node has an edge leading to all higher numbered nodes.

There is precedent for giving a complexity estimate which depends on more than one parameter - http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm quotes a cost of O(|E| + |V| log(|V|). In some cases this might be useful information.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726929

There are two cases here:

  1. m, the number of adjacent nodes is bounded by a constant C, and
  2. m, the number of adjacent nodes is bounded only by n, the number of nodes

In the first case the complexity is O(n), because Log(C) is a constant. In the second case, it's O(n*log(n)) because of the reason that you explained in your question (i.e. "m can be n)).

Upvotes: 3

tu_ru
tu_ru

Reputation: 267

Big O notation provides an upper bound on algorithm's complexity, so since m equals n in the worst case (n - 1 to be precise), the correct complexity would be O(n log n).

Upvotes: 0

Related Questions