Started studying about complexity, I'm struggling with this one:
void what(int n) { int i; for (i = 1; i <= n; i++) { int x = n; while (x > 0) x -= i; } }
Well, the first for loop is clearly O(n)
. The first iteration is O(n)
, second one is O(n/2)
.. and like that log(n)
times I guess? Which means O(n) * O(log(n)) = O(n * log(n)) complexity
. Did I get this right?
Edit: (not a duplicate) I know what Big O is. I've asked the correct evaluation in a specific case.
Sorting approach: Sort the array, this will bring all the duplicates together if present. Now navigate the array and check the adjacent elements to check for duplicates. Time Complexity : O(nlogn) Space Complexity: O(n) by using merge sort. Time Complexity : O(n) and Space Complexity: O(n).
The time complexity of a function (or set of statements) is considered as O(1) if it doesn't contain a loop, recursion, and call to any other non-constant time function. Example: swap() function has O(1) time complexity. A loop or recursion that runs a constant number of times is also considered O(1).
The outer loop runs n
times.
For each iteration, the inner loops runs n / i
times.
The total number of runs is:
n + n/2 + n/3 + ... + n/n
Asymptotically (ignoring integer arithmetic rounding), this simplifies as
n * (1 + 1/2 + 1/3 + ... + 1/n)
This series loosely converges towards n * log(n)
.
Hence the complexity is O(N.log(N)) as you expected.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With