Day 25 of Code: Running Time & Complexity!

[@TheSoulCrisis]

A classical spin on efficiency and space cases and a critical one in the crux of CS! Nice succinct lesson, always nice to keep in mind because it will come in handy several times down the road. :)
Happy I made it through the bulk of the lessons now.....I'll have some great code and projects to reference for my own work later.

[@albertjjimenezp]

I loved this lesson. Greetings from Colombia!

[@branvinivideo]

Good job, thank you!

[@JohnForbes]

Another factor that can determine whether one piece of code is better is the cost (developer time) of production and maintenance of that code.

[@grasshopperweb]

doesn't that fall under elegance?

[@rjcdz06]

Excellent explanation! Thanks.

[@OsaetinEvbuoma]

Thanks for the lesson. On my machine the duration takes longer for v2 than v1. I even tried replacing my code with yours from github and it was still the same. What could possibly cause that? Processing speed, OS? Thanks

[@MAHESHKUMAR_FURONIC]

+Osaetin Evbuoma Try increasing the input by a very large value(more characters) and you must be able to see that at a certain point v1 would take longer time than v2 and after this point, v1 would always take longer time than v2. For Big-O notation we always consider n to be very high.

[@OsaetinEvbuoma]

+MAHESH KUMAR Yes, you're right. Thanks.

[@blondiebytes]

+Osaetin Evbuoma +MAHESH KUMAR That's right. For smaller inputs, v1 might beat v2, but in the long run (with big input), v2 will beat v1.

[@Ed-bf3fe]

On my PC, I kept getting 0ms runtime. If you want more accurate time measurements, replace 'System.currentTimeMillis()' with 'System.nanoTime()'

[@MoineAbdallah]

couldn't you use the V1 and break the inner loop when found a match ?

[@onat2313]

8:14 i was expecting it to take longer aswell xd

[@zhangjing1992]

Hi Kathryn, I have one question.
in 17:13; The findNumsOfRepetitionsv1(); from your descriptions, for each character in char[] c, how many times it appears in our string s.
Would it make more sense to change the code line 26 like this? if( s.charAt(j) == c[i]) { sums[i] = sums[i] + 1; }
Really like your videos, I learn my java again through it. This one seems hard to me , I spends the whole afternoon and night. Assumed I have several questions about Hashtable, but the only left is the first question I wrote down.
Wishes you can do better!~

[@iBlueBro]

Changing the letters i and j around could result in an index out of bounds exception if the string is smaller than the char array. It also wouldn't be checking the letters in the order we expect.
Example:
>>>> pass in string: "hi"
>>>> pass in char[] : {'a', 'b', 'c'}
The way it is done in the video:
if (s.charAt(i) == c[j])
First run through: i = 0, j = 0 : >> if (s.charAt(i) == c[j]) >> if "h" = 'a'
Second run through: i = 0, j = 1: >> if (s.charAt(i) == c[j]) >> if "h" = 'b'
Third run through: i = 0, j = 2: >> if (s.charAt(i) == c[j]) >> if "h" = 'c'
... and then the inner loop finishes, i increases to 1 and points to the letter "i" in "hi." Do all of this again, comparing "i" to 'a', 'b', and 'c'
Your method:
if( s.charAt(j) == c[i]) {
>>>> pass in string: "hi"
>>>> pass in char[] : {'a', 'b', 'c'}
First run through: i = 0, j = 0 : >> if (s.charAt(j) == c[i]) >> if "h" = 'a' >> false
Second run through: i = 0, j = 1: >> if (s.charAt(j) == c[i]) >> if "i" = 'a' >> false
Third run through: i = 0, j = 2: >> if (s.charAt(j) == c[i]) >> Error
Our loops are iterating through the string with i and through the array with j. If we check for the letters in the string using index j and the array using index i, we're not going to get the results we want or expect.

[@zhangjing1992]

Thx, more clear than I expected.
Wish you have a more blondie hair :)

[@fadhilsuhendi8813]

Hi, I need help, I got the runtime error for test case number 8. Do you know why ?

[@amiroz8542]

thanks

[@HariTheHelper]

At what point does v1 take longer I wonder - are we talking thousands of characters, millions? I have tried in the hundreds and placing about 4 times as many characters in v1 than v2, and v2 is still slower.

[@blondiebytes]

+Bob Blake It depends on a lot of things. Say v1 is O(n^2) and v2 is O(n). This means that v2 is faster in the long run. What is the long run? Well it depends on the algorithm. v2 might be slower than v1 in the short run (for testcases with smaller input), but in the long run (with input of millions/thousands of characters) v2 will be faster. Because our inputs are so small here, the way the OS is managing resources could also impact your running time. Since there are so many factors, we narrow it down to runtime complexity based on the input of n to determine if one program is faster than another.

[@blondiebytes]

+Bob Blake Also, our formula for getting the timestamps might be easier during certain instance than others - causing a calculation error, making it unreliable.

[@ande4905]

@@blondiebytes That's what I was thinking too "the way the OS is managing resources" or differences in processor architecture.

[@codersauthority]

I have tried 1 00 000 length of string, still v1 is faster than v2 why?

[@shahidshaon42]

In 18:45 , shouldn't be it (n*m+n) instead of (n*m +1) ??

[@atulacleaver]

I didn't observe any difference in the time in contrast the hashmap one took 1ms while others took 0ms

[@aquaarch41]

Not to be rude, but when you wrote the findNumberOfRepetitionsV2, you declared the 'sum' variable of type int, that was there for no reason at all :)))

[@malibaturhan]

This is a good example I gather before this lesson to try something, sorry for formatting but if you make eclipse format it for you again it will be fine (source ---> format) jpst.it/27sEy

[@blondiebytes]

Great tip!

[@malibaturhan]

@@blondiebytes wow!! thank you : - )

[@MurtagBY]

16:20 (for me to continue)

[@Kahweekah2o2f]

i fixed my own mistake

[@shahidshaon42]

In 18:45 , shouldn't be it (n*m+n) instead of (n*m +1) ??