I have an assignment about algorithms and time complexity and this is the theoretical part that only involves mathematics.
Given an algorithm that belongs to $O(n + k)$, for what values $k$ does the algorithm run in linear time? $n$ and $k$ are positive integers larger than 1. Now, my understanding of linear time comes from the following definition:
Let $T(n)$ and $f(n)$ be two positive functions. We write $T(n) \in O(f(n))$, and say that $T(n)$ has order of $f(n)$, if there are positive constants $M$ and $n_0$ such that $T(n) \leq M \cdot f(n)$ for all $n \geq n_0$.
So if we choose $f(n) = m \cdot n$ for some constant $m$ and can find some $M$ and $n_0$ according to the definition above, it would run in linear time. But it seems to me like I can make an arbitrary condition on $k$, dependent on $n$, to fulfil this. For example, if I would say that for $k \leq \frac12 n$ we have linear time, then $n + k \leq \frac32 n$ which is in $O(n)$ if we pick $M = \frac32$ and $n_0 = 1$. But that we can make any choice isn't problematic in itself, because we would need to find some $k$ for which the linear condition is always true, or do we? Am I overthinking this?
I hope my somewhat confused line of thinking makes at least some sense, and I would be very grateful for any pointers.
The next part is to do the same analysis of $O(n + k \log k)$ which I haven't even gotten started on, but that I guess would use the exact same methodology.
Essentially, you want to solve $k\ln(k) = n $ for $k$.
You can do this iteratively by writing $k(j+1) = \dfrac{n}{\ln(k(j))} $ starting with $k(0) = n$.
Then $k(1) =\dfrac{n}{\ln(n)} $, and $k(2) =\dfrac{n}{\ln\Big(\dfrac{n}{\ln(n)}\Big)} =\dfrac{n}{\ln(n)-\ln(\ln(n))} $.
Since $\dfrac{k(2)}{k(1)} =\dfrac{\dfrac{n}{\ln(n)-\ln(\ln(n))}}{\dfrac{n}{\ln(n)}} =\dfrac{\ln(n)}{\ln(n)-\ln(\ln(n))} \to 1 $, both are good candidates.
$\begin{array}\\ k(1)\ln(k(1)) &=\dfrac{n}{\ln(n)}\ln\Big(\dfrac{n}{\ln(n)}\Big)\\ &=\dfrac{n}{\ln(n)}(\ln(n)-\ln(\ln(n)))\\ &=n-\dfrac{n\ln(\ln(n))}{\ln(n)}\\ &\lt n\\ \end{array} $
and
$\begin{array}\\ k(2)\ln(k(2)) &=\dfrac{n}{\ln(n)-\ln(\ln(n))}\ln\Big(\dfrac{n}{\ln(n)-\ln(\ln(n))}\Big)\\ &=\dfrac{n}{\ln(n)-\ln(\ln(n))}\Big[\ln(n)-\ln(\ln(n)-\ln(\ln(n)))\Big]\\ &=n\dfrac{\ln(n)-\ln(\ln(n)-\ln(\ln(n)))}{\ln(n)-\ln(\ln(n))}\\ &=n\dfrac{\ln(n)-\ln(\ln(n))+\ln(\ln(n))-\ln(\ln(n)-\ln(\ln(n)))}{\ln(n)-\ln(\ln(n))}\\ &=n+n\dfrac{\ln(\ln(n))-\ln(\ln(n)-\ln(\ln(n)))}{\ln(n)-\ln(\ln(n))}\\ &\gt n\\ \end{array} $
Note that
$\begin{array}\\ k(2)\ln(k(2))-n &=n\dfrac{\ln(\ln(n))-\ln(\ln(n)-\ln(\ln(n))))}{\ln(n)-\ln(\ln(n))}\\ &=n\dfrac{-\ln(1-\frac{\ln(\ln(n))}{\ln(n)}))}{\ln(n)-\ln(\ln(n))}\\ &=n\dfrac{\frac{\ln(\ln(n))}{\ln(n)}(1+o(1))))}{\ln(n)-\ln(\ln(n))}\\ &=\dfrac{n}{\ln(n)}\dfrac{\frac{\ln(\ln(n))}{\ln(n)}(1+o(1))))}{1-\frac{\ln(\ln(n))}{\ln(n)}}\\ &=\dfrac{n\ln(\ln(n))}{\ln^2(n)}(1+o(1))\\ \end{array} $