0

Good morning,

I'm trying to find a way to calulate time complexity (average and worst) of greedy algorithm. I know that final formula is: O(nlogn + n) which is O(nlogn). I will appreciate any suggestion/hints how I can calculate this.

Regards

  • 3
    Greedy algorithms defines a set of algorithms that solve a large number of problems using a similar strategy with a variety of time complexities. So you should probably tell us what specific algorithm you're actually talking about. Although you should probably just [read up on big-O notation](http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation), at which point you should have a decent idea of how to figure out the time complexity of any given algorithm. – Bernhard Barker Apr 28 '17 at 16:54
  • Different greedy algorithms have different time complexities. What is the problem here, what is the algorithm, and what is $n$? – Ashwin Ganesan Apr 29 '17 at 04:08

1 Answers1

0

Because the greedy algorithms can be conclude as follows:

Initially let R be the set of all requests，and let A be empty
While R is not yet empty
    Choose a request iR that has the smallest finishing time
    Add request i to A
    Delete all requests from R that are not compatible with request i
EndWhile
Return the set A <is the set of accepted requests

Therefore, the running time of it is consist of:

  1. Sorting the n requests in order, which costs O(nlogn).

  2. Constructing the array containing sorted requests, which costs O(n).

  3. Iterating through the intervals in the array, which costs O(n).

Actually, the second and the third step can often be merged into one step. Thus, the running time of the algorithm is O(nlogn).

(References: Jon,Kleinberg, and Éva,Tardos. Algorithm Design)

Liangyi Zhao
  • 1
  • 1