Timeline for Checking if two strings are anagrams
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 13, 2016 at 22:39 | vote | accept | jellyxbean | ||
| Jul 13, 2016 at 0:48 | comment | added | jellyxbean | yes, it makes sense! thanks so much @Ped7g | |
| Jul 13, 2016 at 0:47 | vote | accept | jellyxbean | ||
| Jul 13, 2016 at 1:07 | |||||
| Jul 12, 2016 at 9:44 | comment | added | Ped7g |
to calculate total complexity of application you just add all Os together, so in your case the input of strings is (2n+2m) (cin+string constructor), then if n!=m we have +1, if n==m there's +(2n.logn) sort, and string == operator is +n again, so total in common case is O(2n+2n+2n.logn+n) = O(5n+2n.logn) = O(n.(5+2.logn)) ... now you "kill" constants, as in big O notation O(5) is same as O(1), so only O(n.logn) remains. You can also imagine it as the biggest complexity eclipses the lesser ones. n*logn is much bigger than n, so O(n+n.logn) is O(n.logn). Just imagine huge n, makes sense?
|
|
| Jul 12, 2016 at 4:29 | answer | added | Zeta | timeline score: 7 | |
| Jul 12, 2016 at 2:11 | comment | added | jellyxbean |
if the C++ function sort() has an average time complexity of O(nlogn), then would this time complexity be O(n)?
|
|
| Jul 12, 2016 at 2:08 | comment | added | jellyxbean |
Oh whoops, totally forgot about calling sort(). Thanks!
|
|
| Jul 12, 2016 at 2:03 | comment | added | Can Nguyen | Like @Greg said, it's not O(1). You can implement the algorithm using character occurence counting but it should be at least O(N) with N = maxlength(one, two) | |
| Jul 12, 2016 at 1:57 | comment | added | Greg Hewgill |
Well, if you've got a call to sort() in there, then it's not going to be O(1).
|
|
| Jul 12, 2016 at 1:35 | history | edited | Jamal | CC BY-SA 3.0 |
deleted 22 characters in body
|
| Jul 12, 2016 at 1:32 | history | asked | jellyxbean | CC BY-SA 3.0 |