import Ġjava . sql . Timestamp Ċ Ċ // Ġbig ĠO Ġis Ġall Ġabout Ġscal ability Ġ- Ġhow Ġdoes Ġthe Ġalgo Ġbehaves Ġwhen Ġth eres Ġa Ġhuge ĠSC ALE . Ċ // CHECK Ġhttps :// www . big oche ats heet . com / Ċ Ċ val Ġn emo Ġ= ĠarrayOf (" n emo ") Ċ Ċ val Ġeveryone Ġ= ĠarrayOf (" d ory ", Ġ" br uce ", Ġ" mar lin ", Ġ" n emo ", Ġ" g ill ", Ġ" b loat ", Ġ" ni gel ", Ġ" squ irt ", Ġ" dar la ", Ġ" h ank ") Ċ Ċ fun Ġmain ( args : ĠArray < String >) Ġ{ ĊĠĠĠ Ġ// find N emo ( every one ) Ġ// ĠO ( n ) Ġ---> ĠLINE AR ĠTIME ĊĊĠĠĠ Ġ// compress First Box ( boxes ) Ġ// as Ġinputs Ġincrease Ġthe Ġoperation Ġwill Ġstill Ġbe Ġ 1 , ĠCONSTANT ĠTIME ĠO ( 1 ) Ġ( GO OD ) ĊĊĠĠĠ Ġ// log First Two Boxes ( boxes ) Ġ// ĠO ( 2 ) Ġ( GO OD ) ĊĊĠĠĠ Ġval Ġbox List Ġ= Ġarray ListOf ( 1 , Ġ 2 , Ġ 3 , Ġ 4 , Ġ 5 ) ĊĊĠĠĠ Ġ// log All Pairs Of Array ( box List ) Ġ// O ( n ^ 2 ) Ġ- Ġnested Ġloops Ġ( Quadr atic ĠTime ) Ġ( H OR R IBLE ) ĊĊĠĠĠ Ġ// as Ġinputs Ġincrease Ġthe Ġnumber Ġof Ġoperations Ġincrease Ġlinear ly Ċ } ĊĊ Ċ fun Ġlog All Pairs Of Array ( box List : ĠArrayList < Int >) Ġ{ ĊĠĠĠ Ġfor Ġ( i Ġin Ġbox List . indices ) Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġbox List . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprint (" Ġ\ n Ġ$ i Ġand Ġ$ j ") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġfind N emo ( array : ĠArray < String >) Ġ{ ĊĠĠĠ Ġval Ġt 0 Ġ= ĠTimestamp ( System . currentTimeMillis ()) ĊĠĠĠ Ġfor Ġ( element Ġin Ġarray ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( element Ġ== Ġ" n emo ") Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprint (" Found ĠN emo ") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġval Ġt 1 Ġ= ĠTimestamp ( System . currentTimeMillis ()) ĊĊĠĠĠ Ġprint (" ĠThat ĠCall Ġtook Ġ: Ġ${ t 1 . time Ġ- Ġt 0 . time }") Ċ } Ċ Ċ fun Ġcompress First Box ( box : ĠArray < String >) Ġ{ ĊĠĠĠ Ġprint ( box [ 0 ]) Ċ } Ċ Ċ val Ġboxes Ġ= ĠarrayOf (" 1 ", Ġ" 2 ", Ġ" 3 ", Ġ" 4 ", Ġ" 5 ") Ċ fun Ġlog First Two Boxes ( box : ĠArray < String >) Ġ{ ĊĠĠĠ Ġprint ( box [ 0 ]) Ġ// ĠO ( 1 ) ĊĠĠĠ Ġprint ( box [ 1 ]) Ġ// ĠO ( 1 ) Ċ } Ċ Ċ // ĠWhat Ġis Ġthe ĠBig ĠO Ġof Ġthe Ġbelow Ġfunction ? Ġ( Hint , Ġyou Ġmay Ġwant Ġto Ġgo Ġline Ġby Ġline ) Ċ fun Ġfun Challenge ( input : ĠArray < Int >): ĠInt Ġ{ ĊĠĠĠ Ġvar Ġa Ġ= Ġ 1 0 ; Ġ// O ( 1 ) ĊĠĠĠ Ġa Ġ= Ġ 5 0 Ġ+ Ġ 3 ; Ġ// O ( 1 ) ĊĊĠĠĠ Ġfor Ġ( element Ġin Ġinput ) Ġ{ Ġ// O ( n ) ĊĠĠĠĠĠĠĠ Ġ// another Function () Ġ// O ( n ) ĊĠĠĠĠĠĠĠ Ġval Ġstr anger Ġ= Ġtrue // ĠO ( n ) ĊĠĠĠĠĠĠĠ Ġa ++ // ĠO ( n ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġa Ġ// ĠO ( 1 ) ĊĠĠĠ Ġ// BIG ĠO Ġnotation Ġ( 3 + 4 n ) Ġ---> > ĠO ( n ) Ċ } Ċ Ċ // ĠWhat Ġis Ġthe ĠBig ĠO Ġof Ġthe Ġbelow Ġfunction ? Ġ( Hint , Ġyou Ġmay Ġwant Ġto Ġgo Ġline Ġby Ġline ) Ċ fun Ġanother Fun Challenge ( input : ĠArray < Int >) Ġ{ ĊĠĠĠ Ġval Ġa Ġ= Ġ 5 ; Ġ// O ( 1 ) ĊĠĠĠ Ġval Ġb Ġ= Ġ 1 0 ; Ġ// O ( 1 ) ĊĠĠĠ Ġval Ġc Ġ= Ġ 5 0 ;// O ( 1 ) ĊĠĠĠ Ġfor Ġ( element Ġin Ġinput ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġx Ġ= Ġelement Ġ+ Ġ 1 ; Ġ// O ( n ) ĊĠĠĠĠĠĠĠ Ġval Ġy Ġ= Ġelement Ġ+ Ġ 2 ;// O ( n ) ĊĠĠĠĠĠĠĠ Ġval Ġz Ġ= Ġelement Ġ+ Ġ 3 ;// O ( n ) ĊĊĠĠĠ Ġ} ĊĠĠĠ Ġfor Ġ( element 2 Ġin Ġinput ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġp Ġ= Ġelement 2 Ġ* Ġ 2 Ġ// O ( n ) ĊĠĠĠĠĠĠĠ Ġval Ġq Ġ= Ġelement 2 Ġ* Ġ 2 Ġ// O ( n ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġval Ġwho Am I Ġ= Ġ" I Ġdon 't Ġknow "; // O ( 1 ) ĊĊĠĠĠ Ġ// total Ġ- ĠO ( 4 + 5 n ) Ġ---> > ĠO ( n ) ĊĊĠĠĠ Ġ// ĠRULE Ġ 1 : ĠBIG ĠO Ġtakes Ġthe Ġworst Ġcase Ġscenario , Ġnot Ġthe Ġbest Ġcase , Ġfinding Ġn emo Ġas Ġa Ġfirst Ġitem Ġin Ġarray Ġis Ġbest Ġcase , ĠAs Ġa Ġlast Ġitem Ġis Ġthe Ġworst Ġcase ĊĠĠĠ Ġ// ĠBIG ĠO Ġdoesnt Ġcare Ġabout Ġanything Ġelse Ġapart Ġfrom Ġworst Ġcase ĊĊĠĠĠ Ġ// ĠRULE Ġ 2 : Ġdrop Ġthe Ġconstants Ġex : ĠO ( 2 n Ġ+ Ġ 3 ) Ġ/ ĠO ( n + 9 0 0 ) Ġ= ĠO ( n ) Ġ( FA IR ) ĊĊĠĠĠ Ġ// RULE Ġ 3 : Ġdifferent Ġinputs Ġhave Ġdifferent Ġterms ĊĠĠĠ Ġfun Ġcompress Boxes Tw ice ( boxes 1 : ĠArray < Int >, Ġboxes 2 : ĠArray < Int >) Ġ{ ĊĠĠĠĠĠĠĠ Ġboxes 1 . forEach Ġ{ Ġprint ( it ) Ġ} Ġ// ĠO ( m ) ĊĊĠĠĠĠĠĠĠ Ġboxes 2 . forEach Ġ{ Ġprint ( it ) Ġ} Ġ// ĠO ( n ) ĊĊĠĠĠĠĠĠĠ Ġ// Total Ġ: ĠO ( m + n ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġnon S ens icle Compress Boxes ( boxes 1 : ĠArray < Int >, Ġboxes 2 : ĠArray < Int >) Ġ{ ĊĠĠĠĠĠĠĠ Ġboxes 1 . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġboxes 2 . forEach Ġ{ Ġprint ( it ) Ġ} Ġ// ĠO ( n * m ) Ġ( H OR R IBLE ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Total Ġ: ĠO ( m * n ) Ġnested Ġloops Ġ- Ġdifferent Ġinputs ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// RULE Ġ 4 : Ġworry Ġabout Ġthe Ġmost Ġdom inant Ġterm ĊĠĠĠ Ġfun Ġprint All Numbers Then All Pairs Sum s ( number : ĠArrayList < Int >) Ġ{ ĊĠĠĠĠĠĠĠ Ġprint (" These Ġare Ġthe Ġnumbers ") ĊĠĠĠĠĠĠĠ Ġnumber . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprint ("\ n Ġ$ it ") Ġ// ĠO ( n ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġprint (" These Ġare Ġtheir Ġsums ") ĊĠĠĠĠĠĠĠ Ġnumber . forEach Ġ{ Ġfirst Number Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnumber . forEach Ġ{ Ġsecond Number Ġ-> Ġfirst Number Ġ+ Ġsecond Number Ġ} Ġ// ĠO ( n ^ 2 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// TOTAL Ġ: Ġ ĠO ( n ) Ġ+ Ġ ĠO ( n ^ 2 ) Ġ= ĠO ( n Ġ+ Ġn ^ 2 ) Ġ-> ĠO ( n ^ 2 ) Ġ--- Ġmost Ġimp Ġterm , ĠDROP ĠTHE Ġin sign ificant Ġterm . ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// O ( n !) ĠO H ĠNO Ġmost Ġexpensive Ġ= ĠFactor ial ĠTime Ġ; Ġadding Ġa Ġnested Ġloop Ġwith Ġevery Ġencounter ĠW OR ST ĠE VER ĊĊĠĠĠ Ġ// O ( n !) ĠO H ĠNO Ġmost Ġexpensive Ġ= ĠFactor ial ĠTime Ġ; Ġadding Ġa Ġnested Ġloop Ġwith Ġevery Ġencounter ĠW OR ST ĠE VER ĊĊĠĠĠ Ġ// O ( 2 ^ n ) Ġ& Ġ ĠO ( n ^ 2 ) Ġ[ A Ġlittle Ġbetter Ġthan Ġ 2 ^ n ] ĠW OR ST ĠTO O ! ĊĊĊĊĠĠĠ Ġ// SPACE ĠCOMP LEX ITY ĊĠĠĠ Ġfun Ġb oooo ( n : ArrayList < Int >) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġhas Ġa Ġspace Ġcomplexity Ġof ĠO ( 1 ) Ġ- Ġsince Ġits Ġa Ġfixed Ġarray ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġn . indices ) Ġ{ Ġprint ( i ) Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġfill Me Up D addy ( n : ĠArrayList < String >): Ġ ĠArrayList < String > Ġ{ ĊĊĠĠĠĠĠĠĠ Ġ// has Ġa Ġspace Ġcomplexity Ġof ĠO ( n ) ĊĠĠĠĠĠĠĠ Ġval Ġhi Array Ġ= ĠArrayList < String >() Ġ// created Ġnew Ġdata Ġstructure ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġn . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhi Array [ i ] Ġ= Ġ" hi " ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġhi Array ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// TR ICK ĠQ UEST ION : Ġwh ats Ġthe Ġlength Ġof Ġa Ġstring Ġ-- Ġdepends Ġon Ġa Ġlanguage Ġin ĠJS Ġits Ġjust Ġa Ġlook Ġup Ġso Ġits ĠO ( 1 ) Ċ } ĊĊĊ