0

I need to compute the big O of my algorithm.

It is contained from two nested for, each of them have binary search tree. the complexity of binary search tree is O(log n)

How can i compute the right complexity of my algorithm ?

Does it O(log(n)log(m)) or O(log(nm)) ?

Roka
  • 9
  • 1
  • Does this answer your question? [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – ChrisGPT was on strike Apr 21 '22 at 21:55
  • 1
    *"the complexity of binary search tree is O(log n)"*: No, a binary search tree is a *data structure*, not an *algorithm*. Algorithms have a time complexity, data structures do not. Without seeing your algorithm in at least a formal language, it is not possible to answer your question. – trincot Apr 25 '22 at 07:21

1 Answers1

0

As you said, one binary search has a complexity of O(log n). You could imagine log(n) as the (maximum) number of steps that your algorithm need. For each of these steps your algorithm performs a nested binary search. That means, you could imagine this as log(n) times log(m) steps.

So you are right with O(log(n) x log(m)).

If for example n is bigger than m, then you have O((log(n))^2).

But normally we don't distinguish between different inputs. We consider them together as "the one" input of size n. Then your complexity is just O((log(n))^2).

Not distinguishing different inputs at least makes sense for polynomial algorithms. To see this consider an example: You have two inputs of sizes n and m with m <= n. Your total input size is therefore n+m. Let's see what happens for different complexities.

  • O(n+m) <= 2*O(n). Normally when talking about complexity we are not interested in constant factors. so we can say, we have O(n).
  • O(log(n+m)) <= O(log(2n)). Now we remember the logarithm rules from school. They say log(2n) = log(2) + log(n). Normally when talking about complexity we are not interested in constants. So we can say, we have O(log(n))
  • O((n+m)^2) = O(n^2+2nm+m^2) <= O(n^2+2nn+n^2) = O(4n^2). Again we are not interested in constant factors and just say, we have O(n^2).
habrewning
  • 735
  • 3
  • 12