4 ms·
Honest question: What would be the complexity of a function that took a string (or array of characters) and called this function on each character? Would it b
by ficklepickle 6y ago
Honest question:
What would be the complexity of a function that took a string (or array of characters) and called this function on each character?
Would it be O(5n) ? Is that a thing? For each additional character in the input, it must compare against 5 values. Or would it be O(n) because it scales linearly?
Thanks in advance. I'm a front end engineer and this is my weakest area but I'm keen to learn. I've studied this before but I use it infrequently and it doesn't stick.
- Tainnor 6y agoO(5n) is the same thing as O(n), because we ignore constant factors in O notation. So, for a fixed size array of vowels, counting the vowels in a string is linear in the length of the string (it can't be sublinear, because we need to look at each character, and the straightforward algorithm is linear).
- formerly_proven 6y ago> O(5n) is the same thing as O(n), because we ignore constant factors in O notation. Even better. f \in O(g) means there is some point and some factor after which f <= c*g. This means O(n²+21371232138091293n) and O(n²) are the same.
- tetha 6y agoYou'll need to be careful what your N is and what you're counting. But lets assume the input is an array of n characters, n being an arbitrarily large but fixed positive number during a single invocation. And we're estimating the number of char compares. Then, each invocation of isVowel(c) will do 1 - 5 compares. 1 in the case that c is the first element of the array, 5 if c is the last element or no element. As a worst-case estimation, isVowel(c) will do 5 compares at worst. As such, if isVowel(c) is called for all elements of A, we will see between n compares (best case for all invocations) and 5*n compares (worst case for all compares). As such, your algorithm has a worst-case runtime of O(5n) for all arrays A, which is a subset of O(n). In practice and outside of academia, that's pretty much all you do: - Identify your input set, and estimate its size - Count how many loops are nested in the algorithm, call that L (1 in this case) - Your algorithm should be O(n^L). Once it gets into amortization and such... it becomes much harder.