What you have coded in your example is very similar to a depth first search. So, that’s one answer. A depth first search algorithm without any special characteristics ( like re-convergent paths that can be optimized out ), should be n^n. This is actually not a contrived example. Chess programs operate on the same algorithm. … Read more
It means that the thing in question (usually running time) scales in a manner that is consistent with the logarithm of its input size. Big-O notation doesn’t mean an exact equation, but rather a bound. For instance, the output of the following functions is all O(n): Because as you increase x, their outputs all increase linearly – if there’s … Read more
Yes, nested loops are one way to quickly get a big O notation. Typically (but not always) one loop nested in another will cause O(n²). Think about it, the inner loop is executed i times, for each value of i. The outer loop is executed n times. thus you see a pattern of execution like this: … Read more
You model the time function to calculate Fib(n) as sum of time to calculate Fib(n-1) plus the time to calculate Fib(n-2) plus the time to add them together (O(1)). This is assuming that repeated evaluations of the same Fib(n) take the same time – i.e. no memoization is used. T(n<=1) = O(1) T(n) = T(n-1) … Read more
Any function whose runtime has the form (log n)k is O((log n)k). This expression isn’t reducable to any other primitive function using simple transformations, and it’s fairly common to see algorithms with runtimes like O(n (log n)2). Functions with this growth rate are called polylogarithmic. By the way, typically (log n)k is written as logk n, so the above … Read more
O( log* N ) is “iterated logarithm“: In computer science, the iterated logarithm of n, written log* n (usually read “log star”), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1.
Just ask wolframalpha if you have doubts. In this case, it says Or you can also calculate the limit yourself: That means n^2 grows faster, so n log(n) is smaller (better), when n is high enough.
Data in an array can be rearranged into a heap, in place. The algorithm for this is actually surprisingly simple., but I won’t go into it here. For a heap sort, you arrange the data so that it forms a heap in place, with the smallest element at the back (std::make_heap). Then you swap the … Read more
In short: Hamiltonian cycle : O(N!) in the worst case WordBreak and StringSegment : O(2^N) NQueens : O(N!) Note: For WordBreak there is an O(N^2) dynamic programming solution. More details: In Hamiltonian cycle, in each recursive call one of the remaining vertices is selected in the worst case. In each recursive call the branch factor decreases by 1. Recursion … Read more
Each partitioning operation takes O(n) operations (one pass on the array). In average, each partitioning divides the array to two parts (which sums up to log n operations). In total we have O(n * log n) operations. I.e. in average log n partitioning operations and each partitioning takes O(n) operations.