It is certainly not possible with a plain singly-linked list. Sketch proof: to examine the last node of a singly-linked list, we must perform n-1 operations of following a “next” pointer [proof by induction on the fact that there is only one reference to the k+1th node, and it is in the kth node, and … Read more
There you go. This is probably the most trivial example of a function that runs in O(n!) time (where n is the argument to the function): void nFacRuntimeFunc(int n) { for(int i=0; i<n; i++) { nFacRuntimeFunc(n-1); } }
I would say it is θ[r (n choose r)], the n choose r part is the number of times the generator has to yield and also the number of times the outer while iterates. In each iteration at least the output tuple of length r needs to be generated, which gives the additional factor r. … Read more
Naive base-conversion as you described takes quadratic time; you do about n bigint-by-smallint divisions, most of which take time linear in the size of the n-bit bigint. You can do base conversion in O(M(n) log(n)) time, however, by picking a power of target-base that’s roughly the square root of the to-be-converted number, doing divide-and-remainder by … Read more
The answer depends strongly on your implementation. For the example you gave there are several possible solutions and I would say that the naive way to implement a solution has better complexity when implemented iterative. Here are the two implementations: int iterative_fib(int n) { if (n <= 2) { return 1; } int a = … Read more
This all depends on the actual implementation used, but I’m basing this on the standard Go as well as gccgo. Slices Reslicing means changing an integer in a struct (a slice is a struct with three fields: length, capacity and pointer to backing memory). If the slice does not have sufficient capacity, append will need … Read more
Simple dfs can do the job. We have a counter set to zero. Start from the root and in each iteration check the value of current node; if it is greater than x, then increase the counter and continue the algorithm for one of the child nodes. The algorithm terminates if counter is bigger than … Read more
You are correct that the outer loop iterates n times and the inner loop iterates n times as well, but you are double-counting the work. If you count up the total work done by summing the work done across each iteration of the top-level loop you get that the first iteration does n work, the … Read more
You can use the merge sort algorithm. In the merge algorithm’s loop, the left and right halves are both sorted ascendingly, and we want to merge them into a single sorted array. Note that all the elements in the right side have higher indexes than those in the left side. Assume array[leftIndex] > array[rightIndex]. This … Read more
Finding articulation vertices is an application of DFS. In a nutshell, Apply DFS on a graph. Get the DFS tree. A node which is visited earlier is a “parent” of those nodes which are reached by it and visited later. If any child of a node does not have a path to any of the … Read more