Looking for a Tutor Near You?

Post Learning Requirement »
x

Choose Country Code

x

Direction

x

Ask a Question

x

x
x
For better view click here
x
Hire a Tutor
DISCOVER

Data Structure And Algorithm

Loading...

Published in: C / C++ | Computer Science | Data Structures
7,137 Views

Time Complexity analysis and derivation using Graphs and Figures.

Prantik S / Kolkata

11 years of teaching experience

Qualification: MCA (Jaipur National University - [JNU], Jaipur - 2017)

Teaches: Basic Computer, Computer for official job, MS Office, School Level Computer, ICT Training, Computer Science, Information Practice, IT & Computer Subjects, BCA Tuition, IT, Computer, C / C++, C# (C Sharp), Java And J2EE, Python Programming, Visual Basic, BCA Subjects, Hardware Training, Networking, Java Script

Contact this Tutor
  1. Asymptotic Notation Growth of Functions and Aymptotic Notation When we study algorithms, we are interested in characterizing them according to their efficiency. We are usually interesting in the order of growth of the running time of an algorithm, not in the exact running time. This is also referred to as the asymptotic running time. We need to develop a way to talk about rate of growth of functions so that we can compare algorithms. Asymptotic notation gives us a method for classifying functions according to their rate of growth. 1
  2. Asymptotic Notation Big-O Notation Definition: f (n) = O(g(n)) iff there are two positive constants c and no such that c for all n 2 no If f (n) is nonnegative, we can simplify the last condition to 0 f (n) cg(n) for all n 2 no We say that "f (n) is big-O of g(n)." As n increases, f (n) grows no faster than g(n). In other words, g(n) is an asymptotic upper bound on f (n). cg(n) f(n) f(n) = O(g(n)) no 2
  3. Asymptotic Notation Example: n2 + n = O(n3) Proof: n2 + n, and g(n) 3 Here, we have f (n) n Notice that if n > 1, n < n3 is clear. Also, notice that if n > 1, n2 < n3 is clear. Side Note: In general, if a b, then na nb whenever n > 1. This fact is used often in these — 2n 3 types of proofs. Therefore, We have just shown that 3 n + n 2n3 for all n 2 1 Thus, we have shown that n2 + n = O(n3) (by definition of Big-O, with no = 1, and c 2.)
  4. Asymptotic Notation Big-Q notation Definition: f (n) = Q(g(n)) iff there are two positive constants c and no such that 2 c for all n 2 no If f (n) is nonnegative, we can simplify the last condition to 0 cg(n) f (n) for all n 2 no We say that "f (n) is omega of g(n)." As n increases, f (n) grows no slower than g(n). In other words, g(n) is an asymptotic lower bound on f (n). f(n) cg(n) f(n) = O(g(n)) no 4
  5. Asymptotic Notation Example: n3 + 4n2 Proof: Q(n2) 5 2 n n3 + 4n2, and g(n) Here, we have f (n) It is not too hard to see that if n > 0, 2 We have already seen that if n 2 1, 3 Thus when n > 1, 2 Therefore, ln2 < n3 + 4n2 for all n > 1 Thus, we have shown that n3 + 4n2 = Q(n2) (by definition of Big-Q, with no = 1, and c 1.)
  6. Asymptotic Notation Big-e notation Definition: f (n) = iff there are three positive constants Cl, c2 and no such that for all n 2 no If f (n) is nonnegative, we can simplify the last condition to 0 Cl g(n) f (n) c2 g(n) for all n 2 no We say that "f (n) is theta of g(n)." As n increases, f (n) grows at the same rate as g(n). In other words, g(n) is an asymptotically tight bound on f (n). f(n) Cl g(n) no 6
  7. Asymptotic Notation Example: Proof: When n > 1, 7 e(n2) n2 + 5n + 7 n2 + 5n2 + 7n When n > 0, n2 < n2 + 5n + 7 Thus, when n > 1 2 < 13n ln2 n2 + 5n 7 13n 2 Thus, we have shown that n2 + 5n + 7 = e(n2) (by definition of Big-e, with no = 1, Cl — 1, and 13.)
  8. Asymptotic Notation Arithmetic of Big-O, Q, and e notations Transitivity: — f (n) e O(g(n)) and — f (n) e and — f (n) e Q(g(n)) and Scaling: if f (n) e O(g(n)) then for any k > 0, f (n) e O(kg(n)) Sums: if fl(n) e O(gl (n)) and f 2 (n) e O ( 92 then (fl + e (n), g2(n)))
  9. Asymptotic Notation Strategies for Big-O Sometimes the easiest way to prove that f (n) = O(g(n)) is to take c to be the sum of the positive coefficients of f (n). We can usually ignore the negative coefficients. Why? Example: To prove 5n2 + 3n + 20 = O(n2), we pick c = 5+3 + 20 = 28. Then ifn 2 no = 1, 5 n2 + 3 n + 20 5 n2 + 3n2 + 20 n2 = 28 n 2 thus 5n2 + 3n + 20 = O(n2). This is not always so easy. How would you show that (v/5)logn + log 2 n + n4 is O(2n)? Or that n2 = O(n2 — 13n + 23)? After we have talked about the relative rates of growth of several functions, this will be easier. In general, we simply (or, in some cases, with much effort) find values c and no that work. This gets easier with practice. 9
  10. Asymptotic Notation Strategies for Q and e Proving that a f (n) = Q(g(n)) often requires more thought. Quite often, we have to pick c < 1. — A good strategy is to pick a value of c which you think will work, and determine which value of no is needed. — Being able to do a little algebra helps. — We can sometimes simplify by ignoring terms of f (n) with the positive coefficients. Why? The following theorem shows us that proving f (n) = is nothing new: — Theorem: f (n) = if and only if f (n) = O(g(n)) and f (n) = Q(g(n)). — Thus, we just apply the previous two strategies. We will present a few more examples using a several different approaches. 10
  11. Asymptotic Notation Show that Ln2 Proof: Notice that if n > 1, —n2 + 3n < Thus, + 3n —n2 + 3n e(n2) —n2 + 3n = O(n2) Also, when n > 0, —n2 < So —n2 + 3n n2 + 3n = Q(n2) Since + 3n = O(n2) and + 3n —n2 + 3n = e(n2) Q(n2),
  12. Asymptotic Notation Show that (n logn — 2n + 13) = Q(n log n) Proof: We need to show that there exist positive constants c and no such that 0 cn logn n logn — 2n + 13 for all n 2 no. n logn — 2n n log n Since — 2 13, we will instead show that cn logn n logn — 2 n, which is equivalent to 2 when n > 1. log n If n 2 8, then 2/(10g n) 2/3, and picking c 1/3 1/3 and no = 8, then for all suffices. Thus if c n 2 no, we have 0 cnlogn n logn — 2n n logn — 2 n + 13. Thus (n logn — 2n + 13) = Q(n log n). 12
  13. Asymptotic Notation Show that Proof: 13 3n = e(n2) We need to find positive constants Cl, Q, and no such that 1 0 Cin —n2 — 3n C2n for all n 2 no Dividing by n2, we get 1 5 1 2 3 — holds for n > 3 n 1/5 10 and Cl 1 3 c2 holds for n 2 1/5, Thus, if Cl all n 2 no, 10 and c2 1. 1, and no = 10, then for 0 —n2 — 3n on for all n 2 no. Thus we have shown that ln2 — 3n = e(n2).
  14. Asymptotic Notation Asymptotic Bounds and Algorithms In all of the examples so far, we have assumed we knew the exact running time of the algorithm. In general, it may be very difficult to determine the exact running time. Thus, we will try to determine a bounds without computing the exact running time. Example: What is the complexity of the following algorithm? for (i for (j O; x; Answer: O(n2) We will see more examples later.
  15. Asymptotic Notation Summary of the Notation f (n) e Q(g(n)) -9 f h g It is important to remember that a Big-O bound is only an upper bound. So an algorithm that is O(n2) might not ever take that much time. It may actually run in O(n) time. Conversely, an Q bound is only a lower bound. So an algorithm that is Q(n log n) might actually be eon). Unlike the other bounds, a e-bound is precise. So, if an algorithm is e(n2), it runs in quadratic time. 15
  16. Asymptotic Notation Common Rates of Growth In order for us to compare the efficiency of algorithms, we need to know some common growth rates, and how they compare to one another. This is the goal of the next several slides. Let n be the size of input to an algorithm, and k some constant. The following are common rates of growth. Constant: e(k), for example 6(1) Linear: e(n) Logarithmic: e(logk n) n log n: logk n) Quadratic: e(n2) Polynomial: e(nk) Exponential: e(/cn) We'll take a closer look at each of these classes. 16
  17. Asymptotic Notation Classification of algorithms - 6(1) Operations are performed k times, where k is some constant, independent of the size of the input n. This is the best one can hope for, and most often unattainable. Examples: int Fifth _ Element (int A [ ] , int n) return A [5] • int Partial _ Sum (int A [ ] , int n) int sum=0 ; for (int i i
  18. Asymptotic Notation Classification of algorithms - e (n) Running time is linear As n increases, run time increases in proportion Algorithms that attain this look at each of the n inputs at most some constant k times. Examples: void sum_first_n (int n) { int i, sum=0; for (i = 1; i
  19. Asymptotic Notation Classification of algorithms - e (log n) A logarithmic function is the inverse of an exponential function, i.e. bC = n is equivalent to x = logb n) Always increases, but at a slower rate as n 1 increases. (Recall that the derivative of log n is a decreasing function.) Typically found where the algorithm can systematically ignore fractions of the input. 19 Examples: int binary search (int a [ ] int 1=1, r=n, m; while (r>=l) int n, int val) if if (a [m] return m; (a [m] >val) r=m—l; else 1=m+1; return —1;
  20. Asymptotic Notation Classification of algorithms - e (n log n) Combination of O(n) and O(log n) Found in algorithms where the input is recursively broken up into a constant number of subproblems of the same type which can be solved independently of one another, followed by recombining the sub-solutions. Example: Quicksort is O(n log n). Perhaps now is a good time for a reminder that when speaking asymptotically, the base of logarithms is irrelevant. This is because of the identity loga b logb n = logan. 20
  21. Asymptotic Notation Classification of algorithms - e(n2) We call this class quadratic. As n doubles, run-time quadruples. However, it is still polynomial, which we consider to be good. Typically found where algorithms deal with all 21 pairs of data. Example: int *compute _ sums (int A [ ] int M [n] [n]; int i, j; for (i i
  22. Asymptotic Notation Classification of algorithms - e(2n) We call this class exponential. This class is, essentially, as bad as it gets. Algorithms that use brute force are often in this class. Can be used only for small values of n in practice. Example: A simple way to determine all n bit numbers whose binary representation has k non-zero bits is to run through all the numbers from 1 to 2n, incrementing a counter when a number has k nonzero bits. It is clear this is exponential in n. 22
  23. Asymptotic Notation Comparison of growth rates 10.75 13.62 16.64 19.78 23.03 26.38 36.95 40.62 23 log n 0 0.6931 1.099 1.386 1.609 1.792 1.946 2.079 2.197 2.303 2.398 2.485 2.565 2.639 2.708 2.773 2.833 2.890 log log m n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 log m n log n 0 1.39 3.30 5.55 8.05 29 .82 .34 33 44.36 48.16 52.03 2 n 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 3 n 1 8 27 64 125 216 343 512 729 1000 1331 1728 2197 2744 3375 4096 4913 5832 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
  24. Asymptotic Notation n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 More growth rates 100n 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 n 1 4 9 25 36 49 100 121 144 169 196 225 256 289 324 361 11n2 11 99 176 275 396 539 704 891 1100 1331 1584 1859 2156 2475 2816 3179 3564 3971 3 1 8 27 125 216 343 512 729 1000 1331 1728 2197 2744 3375 4096 4913 5832 6859 2 4 8 32 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288
  25. Asymptotic Notation More growth rates n 2 6 22 26 30 34 38 42 46 50 54 62 66 70 74 2 n 4 36 100 196 324 484 676 900 1156 1444 1764 2116 2500 2916 3364 3844 4356 4900 5476 2 n ? " " 2 ? 99 2 30 90 182 306 462 650 870 1122 1406 1722 2070 2450 2862 3306 3782 4290 4830 5402 103 135 199 295 423 583 775 999 1255 1543 1863 2215 2599 3015 3463 3943 4455 4999 5575 3 8 216 1000 2744 5832 10648 17576 27000 39304 54872 74088 97336 125000 157464 195112 238328 287496 343000 405224 ? 234 242 450 1234 2978 6066 10882 17810 27234 39538 55106 74322 97570 125234 157698 195346 238562 287730 343234 405458
  26. Asymptotic Notation Polynomial Functions 40000 35000 x * 3 30000 x * 4 · 25000 20000 15000 10000 5000 0 25 5 0 20 30 40
  27. Asymptotic Notation Slow Growing Functions 250 log(x) - 200 150 100 25 20 30 40
  28. Asymptotic Notation Fast Growing Functions Part 1 5000 4500 x*V4 4000 2 x 3500 3000 2500 2000 1500 1000 500 0 6 0 2 4 8
  29. Asymptotic Notation Fast Growing Functions Part 2 500000 X 450000 x**3 x**4 400000 2**x 350000 300000 250000 200000 150000 100000 50000 0 5 0 20
  30. Why Constants and Non-Leading Terms Don't Matter 4e+08 3.5e+08 3e+08 2.5e+08 2e+08 1 e-1-08 5e+07 O 5 10 1000000*x 15 25 20 30
  31. Asymptotic Notation Classification Summary We have seen that when we analyze functions asymptotically: Only the leading term is important. Constants don't make a significant difference. The following inequalities hold asymptotically: c < logn < log n < n < n < n logn (1.1) n < n logn < n In other words, an algorithm that is log(n)) is more efficient than an algorithm that is e (n3). 31

Need a Tutor or Coaching Class?

Post an enquiry and get instant responses from qualified and experienced tutors.

Post Requirement

Related Study Notes

Upload Study Notes

If you have your own Study Notes which you think can benefit others, please upload on LearnPick. For each approved Study Note you will get 100 Credit Points and 100 Activity Score which will increase your profile visibility.

Upload Now
Home > Study Notes > Data Structure And Algorithm