3

The complexity is $O(n)$. What is $O(1)$ is the time it takes to access a cell in the hash table. By the way, assuming that each character is a byte, you can just use a plain old array of length 256.


3

I think this is a common misconception among undergraduates about $\mathcal{O}$, $\Omega$, and $\Theta$. It is not like these symbols represent worst, best, and average case running time, respectively. They are just upper and lower bounds on running times and you can have lower and upper bounds on all of those cases. In some sense, $\Omega$ is just the ...


2

If the maximum element is the $n$'th, then $\text{maxNum}$ is not necessarily updated n times. Consider for example the case where the second largest element is in first position. Then $\text{maxNum}$ is updated twice no matter where the largest element is. Let $U_n$ be the average number of updates of $\text{maxNum}$ for a list of size $n$. Let $i_\max$ ...


2

Let me start with your main question "where my mistake took place exactly?" - in short, the whole point is in the wrong choice of the probability distribution for $Pr(t_n=t)$. You are considering the number of changes in the maximum, i.e. how many times maxNum was updated, but you are using probabilities for the location the maximum in the array. ...


1

By showing a worst-case example, it doesn't show $O(mn)$ ... big-O is an upper bound, so when asserting a big-O runtime, it says that that algorithm takes $O(mn)$ time or better (remember that an $O(n)$ algorithm is also an $O(n^2)$ algorithm). But showing that there is an example that actually requires $kmn$ time means that the big-O runtime of $O(mn)$ ...


1

It is difficult to avoid what is repeating what is in the text, but you have exactly: $T(n) = (n-1)+(n-2)+\ldots+1+0 =n\tfrac{n-1}{2} = \tfrac12n^2 -\tfrac12n$ and as an upper bound taking each value up to $n-1$: $T(n) \le (n-1)+(n-1)+\ldots+(n-1)+(n-1) =n(n-1) = n^2-n$ and as an lower bound taking values of at least $\tfrac n2$ down to $\tfrac n2$ and other ...


Only top voted, non community-wiki answers of a minimum length are eligible