For what values $k$ are $O(n + k)$ and $O(n + k \log k)$ linear? 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.
 A: 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}
$
