What is the difference between time complexity of O(n) and O(Log n). Let's say I have a function which has time complexity of O(Log n) and space complexity of n.
What will be the time complexity if I have to calculate addition of two functions with time complexities of:
Don't bother with the constant term. We are only interested in scaling behaviours, i.e.
What happens to the overall space or time, when we have n times more?
If the space or time required goes up by the same factor, it is O(n).
If it goes upby a constant additive step for every scale factor of input size, we say it is O(log N). For example, for sizes of 1, 10, 100, the times may be 4 sec, 4.5 sec, 5 sec. Then you are adding 0.5 seconds for every 10-fold increase in data.
If it goes up by the square of that factor, it is O(n^2).
You raise an excellent question:
Will it not be Log n * Log n -> log^2(n) = log(n)×log(n) = log(n)^2?
I am looking at this answer quora.com/Difference-between-log-2-n-log-log-n-and-log-n-2 qr.ae/pr3wPd
That is the wrong arithmetic.
You were asking about a process that involved two subprocesses that have to happen one-after-another. So the time taken is the addition, not the multiplication.
What you want to calculate is
log N + log N = 2 log N
But for O notation, we disregard the 2, and just write the result as O(log N).
O()As pointed out by @Support Ukraine in the comments:
If an algorithm which is O(log n) calls (in its innermost loop) another algorithm which is also O(log n), then the resulting complexity is O((log n) ^2).
If your process involves doing an O(N) thing, and then once that has finished, doing an O(log N) thing, then the overall result is O(N).
This is because once N gets large, the N will grow much faster than log N.
When you say something is proportional to something else, you don't really care about any constant terms.
Suppose the amount people eat is proportional to their weight. You can say that, without specifying how many meals, days, or years we are talking about. The duration will affect the constant of proportionality but not the concept that "cost of food eaten" is proportional to "body weight".
For example, if you switch between currencies, or add taxes, the constant of proportionality changes, but the proportionality remains.