CODEWITHSUNDEEP
performancecomplexity-theorytime-complexity
Mhsz
Mhsz

Reputation: 233

which algorithm is better time complexity?

I read about Big-O notation. I understood some idea but when compared two algorithm I don't understood some thing look following he say existing two algorithm.

 First f2(n) = 2n + 20 steps. 
second f3(n) = n + 1 steps.
he write f2 = O(f3):

    f2(n)/f3(n)
    =((2n + 20)/(n + 1))<= 20;
   he say Certainly f3 is better than f2?, of course f3 = O(f2), this time with c = 1.

I think f3 is better than f2 because less factors. my questions

1) why constant c= 1 how he pick that? 2) why f3 = O(f2) and why f2 = O(f3) ?

Upvotes: 1

Views: 362

Answers (2)

Nik Bougalis
Nik Bougalis

Reputation: 10613

Patrick87's answer explains a little more about the asymptotic nature of Big-O notation. I will show you a bit more analysis of this. Let's examine f2 and f3 a bit more closely:

First, f2(n): We know that f2(n) = O(2n + 20). The 20 is a constant, so we can ignore it. So, f2(n) = O(2n + 20) = O(2n). Again, the 2 is a constant, so we can also ignore it, so: f2(n) = O(2n + 20) = O(2n) = O(n).

What this analysis means is that as n increases, a function that is 2n + 20 grows as fast as a function that is 2n, which grows as fast as a function that is n. This makes sense if you think about it: all these functions are parallel lines. Their rate of growth is the same.

Now f3(n): We know that f3(n) = O(n + 1). The 1 is a constant, so we can ignore it. So, f3(n) = O(n).

And that is why f3 and f2 are both O(n). This doesn't mean that these functions take the exact same time for a given value of n, or that f2 is as fast as f3 in clock time. It just means that the complexity (i.e. the time they take to do work) of both functions increases at the same rate as n increases.

Upvotes: 0

Patrick87
Patrick87

Reputation: 28332

These are both linear functions, so both are O(n), and both O of each other. f3 is 20 times faster, asymptotically, than f2. All these things are simultaneously true.

Upvotes: 1

Related Questions