CODEWITHSUNDEEP
big-otime-complexity
userNotFound
userNotFound

Reputation: 347

Algorithmic Upper Bound for my solution

I'm working on some homework and I want to make sure my analysis of the upper bound for the solution is correct.

Here's what I do.

  1. I read n characters from an input string. // O(n)
  2. Construct a min heap of size k(where k is a large constant). // O(n)
  3. Retreive the k entries from the min heap. // O(k *log n).

The complexity of my solution is therefore O(n+ k·logn). I was wondering whether I can safely approximate to O(n), if I take into consideration that k is a constant.

Upvotes: 0

Views: 42

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

Yes, if k is a constant, then Θ(n + k log n) = Θ(n) + Θ(k log n) = Θ(n) + Θ(log n) = Θ(n).

Upvotes: 1

Related Questions