# Time and Space complexity  --- ## Our reactions to this spike  --- ## What did we learn today?  --- ### Our Chats Discoveries - Vatsal and Kat both did Maths in the same year at the same uni and were in the same algebra lecture, they also both have amazing gardens :herb: - There are lots of different species of mint and basil - There might be thunderstorms on Friday :thunder_cloud_and_rain:  --- - Clubs in Seoul only closed down last month :dancer: - Kids in korea like Brawl Stars and have their own phones - Ina's English teacher cussed her out for not knowing English words and traumatised her :scream_cat:  --- ### P, NP - How much time a problem takes is categorised broadly in "complexity classes". - P "polynomial time" ('fast'). (e.g. O(x3)) - NP "non-polynomial time" ('slow') (a lot of security relies on NP problems...e.g. prime factorisation) --- - $1,000,000 for showing that P is not equal to NP. - If one shows that P=NP then it means that if you can solve any NP problem it means you have automatically solve all of them. - NL -> P -> NP -> PSPACE -> EXPTIME -> EXPSPACE. --- ### travelling salesman problem Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" - this is an NP problem. - google maps --- ## O(n) arr=[1, 2, 3, 4, 5], x=3 ```javascript= function FindIndexOfX(arr, x){ for(let i=0; i<arr.length; i++) { if(arr[i] === x) { return i } } } ``` #### ```O(arr.length) => O(n), Omega(1)``` --- ## O(n^2), where n is the size of the array arr=[[1, 2, 4], [3, 4, 5], [2, 5, 7]], x=3 ```javascript= function FindIndexOfX(arr, x){ for(let i=0; i<arr.length; i++) { for (let j=0; j< arr[i].length;j++) { if(arr[i][j] === x) { return [i, j] } } } } ``` --- n=3 O(n) * O(n) => O(n^2), Omega(1) --- ## O(n^2), where n is the size of the largest subarray arr=[[1, 2], [3, 5, 6], [4, 5, 2, 2]], x=3 ```javascript= function FindIndexOfX(arr, x){ for(let i=0; i<arr.length; i++) { for (let j=0; j< arr[i].length;j++) { if(arr[i][j] === x) { return [i, j] } } } } ``` --- #### ```O(n=3) * (O(n=2) + O(n=3) + O(n=4) ) => O(n=4^2), Omega(1)``` ``` m = arr.length n_i = arr[i].length O(m*sum_i(n_i)) = O(max(n_i, m)) ``` --- ### Answers? to some questions - Why does any of this matter? - Efficiency - Where do data structures fit into this discussion? - Different data structures, i.e. arrays and objects are better at different things --- - How might we address these issues in our code? - Avoid doing loops within loops, O(n2)... - Does time or space matter more than the other? - It depends.... --- ## Any questions?