Shawn Zhong

Shawn Zhong

 钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • AP Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Shawn Zhong

 钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • AP Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

3.3 Complexity of Algorithms

Home / 2018 / February / 28 / 3.3 Complexity of Algorithms

3.3 Complexity of Algorithms

  • Feb 28, 2018
  • Shawn
  • Math 240
  • No comments yet

The Complexity of Algorithms • Given an algorithm, how efficient is this algorithm for solving a problem given input of a particular size? • To answer this question, we ask: ○ How much time does this algorithm use to solve a problem? ○ How much computer memory does this algorithm use to solve a problem? • When we analyze the time the algorithm uses to solve the problem given input of a particular size, we are studying the time complexity of the algorithm. • When we analyze the computer memory the algorithm uses to solve the problem given input of a particular size, we are studying the space complexity of the algorithm. • In this course, we focus on time complexity. • The space complexity of algorithms is studied in later courses. • We will measure time complexity in terms of the number of operations an algorithm uses and we will use big-O and big-Theta notation to estimate the time complexity. • We can use this analysis to see whether it is practical to use this algorithm to solve problems with input of a particular size. • We can also compare the efficiency of different algorithms for solving the same problem. • We ignore implementation details because it is extremely complicated to consider them. Time Complexity • To analyze the time complexity of algorithms, we determine the number of operations, such as comparisons and arithmetic operations (addition, multiplication, etc.). • We can estimate the time a computer may actually use to solve a problem using the amount of time required to do basic operations. • We ignore minor details, such as the “house keeping” aspects of the algorithm. • We will focus on the worst-case time complexity of an algorithm. • This provides an upper bound on the number of operations an algorithm uses to solve a problem with input of a particular size. • It is usually much more difficult to determine the average case time complexity of an algorithm. • This is the average number of operations an algorithm uses to solve a problem over all inputs of a particular size. Complexity Analysis of Algorithms • Example: Describe the time complexity of the algorithm for finding the maximum element in a finite sequence. ○ Count the number of comparisons. ○ The max a_i comparison is made n − 1 times. ○ Each time i is incremented, a test is made to see if i≤n. ○ One last comparison determines that i>n. ○ Exactly 2(n−1)+1=2n−1 comparisons are made. ○ Hence, the time complexity of the algorithm is Θ(n). • Example: Determine the time complexity of the linear search algorithm. ○ Count the number of comparisons. ○ At each step two comparisons are made; i≤n and x≠a_i . ○ To end the loop, one comparison i≤n is made. ○ After the loop, one more i≤n comparison is made. ○ If x=a_i, 2i+1 comparisons are used. ○ If x is not on the list, 2n+1 comparisons are made and then an additional comparison is used to exit the loop. ○ So, in the worst case 2n+2 comparisons are made. ○ Hence, the complexity is Θ(n). • Example: Describe the average case performance of the linear search algorithm. ○ Assume the element is in the list and that the possible positions are equally likely. ○ By the argument on the previous slide, if x=a_i , the number of comparisons is 2i+1 ○ (3+5+7+…+(2n+1))/n=(2(1+2+3+…+n)+n)/n=2[n(n+1)/2]/n+1=n+2 ○ Hence, the average-case complexity of linear search is Θ(n). • Example: Describe the time complexity of binary search in terms of the number of comparisons used. ○ Assume (for simplicity) n = 2^k elements. Note that k=log⁡n. ○ Two comparisons are made at each stage; i<j, and x>a_m. ○ At the first iteration the size of the list is 2k and after the first iteration it is 2k−1. ○ Then 2k−2 and so on until the size of the list is 2^1=2. ○ At the last step, a comparison tells us that the size of the list is the size is 2^0=1 and the element is compared with the single remaining element. ○ Hence, at most 2k+2=2 log⁡n+2 comparisons are made. ○ Therefore, the time complexity is Θ (log⁡n), better than linear search. • Example: What is the worst-case complexity of bubble sort in terms of the number of comparisons made? ○ A sequence of n−1 passes is made through the list. ○ On each pass n−i comparisons are made. ○ (n−1)+(n−2)+…+2+1=n(n−1)/2=1/2 n^2−1/2 n ○ The worst-case complexity of bubble sort is Θ(n^2) • Example: What is the worst-case complexity of insertion sort in terms of the number of comparisons made? ○ The total number of comparisons are ○ 2+3+…+n=n(n−1)/2−1 ○ Therefore the complexity is Θ(n^2) • Example: How many additions of integers and multiplications of integers are used by the matrix multiplication algorithm to multiply two n×n matrices. ○ There are n^2 entries in the product. ○ Finding each entry requires n multiplications and n−1 additions. ○ Hence, n^3 multiplications and n^2 (n−1) additions are used. ○ Hence, the complexity of matrix multiplication is O(n^3). Understanding the Complexity of Algorithms Complexity of Problems • Tractable Problem ○ There exists a polynomial time algorithm to solve this problem. ○ These problems are said to belong to the Class P. • Intractable Problem ○ There does not exist a polynomial time algorithm to solve this problem • Unsolvable Problem ○ No algorithm exists to solve this problem, e.g., halting problem. • Class NP ○ Solution can be checked in polynomial time. ○ But no polynomial time algorithm has been found for finding a solution to problems in this class. • NP Complete Class ○ If you find a polynomial time algorithm for one member of the class, ○ it can be used to solve all the problems in the class. P Versus NP Problem • The P versus NP problem asks whether the class P = NP? • Are there problems whose solutions can be checked in polynomial time, but can not be solved in polynomial time? • Note that just because no one has found a polynomial time algorithm is different from showing that the problem can not be solved by a polynomial time algorithm. • If a polynomial time algorithm for any of the problems in the NP complete class were found, then that algorithm could be used to obtain a polynomial time algorithm for every problem in the NP complete class. • Satisfiability (in Section 1.3) is an NP complete problem. • It is generally believed that P≠NP since no one has been able to find a polynomial time algorithm for any of the problems in the NP complete class. • The problem of P versus NP remains one of the most famous unsolved problems in mathematics (including theoretical computer science). • The Clay Mathematics Institute has offered a prize of $1,000,000 for a solution.’ class=’alignnone size-full wp-image-4251 ‘ src=’https://shawnzhong.com/wp-content/uploads/2018/02/img_5a96d14e5fb4d.png’ /></p> </div> <div class="entry-footer"> </div> </div> </article> <div class="post-attributes"> <!--Related Posts--> <div class="related-posts"> <h3>Related Posts</h3> <div class="multi-carousel onetone-related-posts owl-carousel owl-theme"> <div class="owl-item"> <div class="post-grid-box"> <div class="img-box figcaption-middle text-center from-left fade-in"> <a href="https://shawnzhong.com/2018/01/30/math-240/"> <img src="https://shawnzhong.com/wp-content/uploads/2018/01/0876df69-2866-4428-9fc3-a97d8d0cf81e-8969a864474f.small_.jpg" class="feature-img"/> <div class="img-overlay"> <div class="img-overlay-container"> <div class="img-overlay-content"> <i class="fa fa-link"></i> </div> </div> </div> </a> </div> <div class="img-caption"> <a href="https://shawnzhong.com/2018/01/30/math-240/"><h4>Math 240</h4></a> <ul class="entry-meta"> <li class="entry-date"><i class="fa fa-calendar"></i>January 30, 2018</li> <li class="entry-author"><i class="fa fa-user"></i>Shawn</li> </ul> </div> </div> </div> </div> </div> <!--Related Posts End--> <!--Comments Area--> <div class="comments-area text-left"> <!-- If comments are open, but there are no comments. --> <div id="respond" class="respondbg"> <div id="respond" class="comment-respond"> <h3 id="reply-title" class="comment-reply-title">Leave a Reply <small><a rel="nofollow" id="cancel-comment-reply-link" href="/2018/02/28/3-3-complexity-algorithms/#respond" style="display:none;">Cancel reply</a></small></h3><form action="https://shawnzhong.com/wp-comments-post.php" method="post" id="commentform" class="comment-form" novalidate><p class="comment-notes">Your email address will not be published.</p><div class="clear"></div><p class="form-allowed-tags"></p> <section class="comment-form-comment form-group"><div id="comment-textarea"><textarea id="comment" name="comment" placeholder="Message" cols="45" rows="8" class="textarea-comment form-control" aria-required="true"></textarea></div></section><div class="row"><section class="comment-form-author form-group col-md-4"><input id="author" class="input-name form-control" name="author" placeholder="Name" type="text" value="" size="30" aria-required=

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  • 3.2 The Growth of Functions
  • Math 541 – 2/28

Search

  • Home Page
  • Tutorials
  • Mathematics
    • Math 240 – Discrete Math
    • Math 375 – Linear Algebra
    • Math 431 – Intro to Probability
    • Math 514 – Numerical Analysis
    • Math 521 – Analysis I
    • Math 541 – Abstract Algebra
    • Math 632 – Stochastic Processes
    • Abstract Algebra @ 万门大学
    • Linear Algebra @ 万门大学
    • Category Theory
  • Computer Sciences
    • CS/ECE 252 – Intro to Computer Engr.
    • CS/ECE 352 – Digital System Fund.
    • Learn Haskell
  • Course Notes
    • AP Macroeconomics
    • AP Microeconomics
    • AP Chemistry
    • AP Statistics
    • AP Physics C: E＆M
    • AP Physics C: Mechanics
    • CLEP Psychology
  • 2048 Game
  • HiMCM 2016
  • 登峰杯 MCM

WeChat Account

Categories

  • Notes (418)
    • AP (115)
      • AP Macroeconomics (20)
      • AP Microeconomics (23)
      • AP Physics C E＆M (25)
      • AP Physics C Mechanics (28)
      • AP Statistics (19)
    • Computer Sciences (2)
    • Mathematics (300)
      • Abstract Algebra (29)
      • Category Theory (7)
      • Linear Algebra (29)
      • Math 240 (42)
      • Math 375 (71)
      • Math 514 (18)
      • Math 521 (39)
      • Math 541 (39)
      • Math 632 (26)
  • Projects (2)
  • Tutorials (11)

Archives

  • October 2019
  • May 2019
  • April 2019
  • March 2019
  • February 2019
  • December 2018
  • November 2018
  • October 2018
  • September 2018
  • July 2018
  • May 2018
  • April 2018
  • March 2018
  • February 2018
  • January 2018
  • December 2017
  • November 2017
  • October 2017
  • September 2017
  • August 2017
  • July 2017
  • June 2017

WeChat Account

Links

RobeZH's thoughts on Algorithms - Ziyi Zhang
Copyright © 2018.      
TOP