TimeAndSpaceComplexity

50 %
50 %
Information about TimeAndSpaceComplexity
Education

Published on March 9, 2014

Author: lakshmitharun

Source: authorstream.com

Time and Space Complexity: Time and Space Complexity Justin Kovacich What are they, exactly?: What are they, exactly? Time Complexity – The amount of time required to execute an algorithm Space Complexity – The amount of memory required to execute an algorithm. Big O Notation: Big O Notation Used to describe the amount of time a given algorithm would take in the worst case, based on the input size n. For the sake of analysis, we ignore constants: O(C * f(n)) = O(g(n)) or O(5N) = O(N) Algorithm Analysis Time!: Algorithm Analysis Time! void bubblesort ( int []array, int len ){ boolean unchanged = false; while(unchanged == false) { unchanged = true; for( int i = 0; i < len -1; i ++) if(a[ i ] > a[i+1]){ swap (a[ i ], a[i+1]) unchanged = false; } } } Sample data, lets follow along!: Sample data, lets follow along! 6 5 4 3 2 1 Totals: 5 4 3 2 1 6 5 swaps 4 3 2 1 5 6 4 swaps + 1 skip 3 2 1 4 5 6 3 swaps + 2 skips 2 1 3 4 5 6 2 swaps + 3 skips 1 2 3 4 5 6 1 swap + 4 skips 1 2 3 4 5 6 5 skips The following represents a sample input array of size n = 6 to our bubble sort algorithm. This is a look after each pass of the for loop, where it must go from 0 to n -1. Time to add it up…: Time to add it up… 2 + 4(n-1) + 2 + 4(n-2) + 2(i) + … + 2 + 2(n-1) N loops through while *(N-1 ) loops through for = N 2 – N As size of N grows larger, only the N 2 factor is important. O(f(n)) = O(N 2 ) The best case for any sort algorithm is O(N), and bubblesort can achieve that if its data is already sorted. On average, it is one of the worse sorting algorithms. Other Ways to Measure Time Complexity: Other Ways to Measure Time Complexity The Average Case – More difficult to compute because it requires some knowledge of what you should expect on average, but is a best measure of an algorithm. Bubble sort shares the same worst case time complexity with insertion sort, but on average is much worse. The Best Case – Not exactly the best measure of an algorithm’s performance because unless it is likely to continually be the best case comparisons between algorithms are not very meaningful. A quick look at Space Complexity: A quick look at Space Complexity In our previous example, our array consisted of an n integer array, and 3 other variables. Space complexity is typically a secondary concern to time complexity given the amount of space in today’s computers, unless of course its size requirements simply become too large. Why is time complexity important?: Why is time complexity important? Allows for comparisons with other algorithms to determine which is more efficient. We need a way to determine whether or not something is going to take a reasonable amount of time to run or not…Time complexities of 2 n are no good. For n = 100, would be 1267650600228229401496703205376 operations (which would take a super long time.) Time Complexity, the bigger picture.: Time Complexity, the bigger picture. One of the big questions in Computer Science right now is the finding a way to determine if an NP-Complete problem can be computed in polynomial time. NP-Complete problems are problems that cannot, to our knowledge, be solved in polynomial time, but whose answer can be verified in polynomial time. Homework Assignment!: Homework Assignment! Without any fore-knowledge of the data you’re going to be operating on, what is the best case time complexity for a sorting algorithm and why? References: References Dewdney, A.K. The New Turing Omnibus. New York: Henry Holt, 1989. 96 – 102 “Computational Complexity Theory”, Wikipedia, http://en.wikipedia.org/wiki/Computational_complexity_theory . Accessed 1/28/08, last modified 1/15/08.

Add a comment

Related presentations

Related pages

TimeandSpaceComplexity ofReversiblePebbling

TimeandSpaceComplexity ofReversiblePebbling Richard Kr´al’oviˇc DepartmentofComputerScience FacultyofMathematics,PhysicsandInformatics ...
Read more

ALID: Scalable Dominant Cluster Detection

ALID: Scalable Dominant Cluster Detection Lingyang Chu Key Lab of Intell. Info. ... timeandspacecomplexity. Second,weestimateaRegionofInterest(ROI)andpro-
Read more

SyllabusforCPSC465/565 - Yale University

SyllabusforCPSC465/565 Spring2016 Instructor: JamesAspnes ... logicalandgeometricconstraints,timeandspacecomplexity,anddistributed algorithms. Meetingtimes
Read more

Contents - beck-shop.de

x Contents 13 Complexity Theory ... 13.2 TimeandSpaceComplexity ..... 252 13.2.1 OnMeasuringTimeComplexity ..... 253 13.2.2 OnMeasuringSpaceComplexity ...
Read more

Online Multitasking and User Engagement - Janette Lehmann

Online Multitasking and User Engagement Janette Lehmann ... timeandspacecomplexity. Eachpairofconnectednodesis thenlabeledbyoneofthefollowings:
Read more

www.nds.rub.de

www.nds.rub.de
Read more

Principles of Model Checking

Principles of Model Checking Christel Baier Joost-Pieter Katoen The MIT Press Cambridge, Massachusetts London, England
Read more

Complexity and Approximation - Toc

Complexity and Approximation Combinatorial Optimization Problems and Their Approximability Properties Bearbeitet von Giorgio Ausiello, Pierluigi Crescenzi ...
Read more

OntheAppropriatenessofNegativeSelectionforAnomaly ...

OntheAppropriatenessofNegativeSelectionforAnomaly DetectionandNetworkIntrusionDetection Dissertationsschrift inenglischerSprache vorgelegt ...
Read more