I am a bit confused as to how to look for the Big-O of this algorithm.  So far I'm thinking that the while loop wouldn't be O(n) like a normal iteration of an array since x doubles after each for loop. The mergeSort is n log n, and I have no idea how to go about the for loop's time complexity. I don't think its O(n) either, since once again, x doubles.  void algorithm2 (int[] A, int n) {    int x = 1;   while (x &lt; n) {      for (int i = 0; i + x &lt; n; i += 2 * x ) {       mergeSort(A, i , i + x -1, i + 2 * x - 1);     }      x = x * 2;   } }    Any help would be greatly appreciated!
304
Most people with a degree in CS will certainly know what . It helps us to measure how well an algorithm scales.   But I'm curious, how do you calculate or approximate the complexity of your algorithms?
62978
Using the recursion tree i tried solving this: $T(n)=T(n-1)+T(\frac{n}{2})+n$; the tree has two parts (branches) one that of $T(n-1)$ and other branch is of $T(\frac{n}{2})$. But as the term T(n-1) reach higher depth, I solved that part of the tree. Finally it resulted in O$(2^n)$ is it correct or is it $O(n^2)$? How can we solve it by substitution method?
48763
I got this from "4.4 The recursion-tree method for solving recurrences" in book "Introduction to Algorithms"  The recurrence that try to use recursion-tree to solve is: $T(n) = 3T(n/4) + cn^2$
6362
I need to calculate the time complexity of the following code:  for (i = 1; i &lt;= n; i++) {   for(j = 1; j &lt;= i; j++)   {    // Some code   } }   Is it O(n^2)?
124219
The passage said that the computational load to attack DES-X can be reduced to approximately $2^{(56+64)}=2^{120}$ steps,and  the storage of data sets should be $2^{64}$.  But I can't figure why it is time complexity $2^{120}$ and  the (space complexity) of data sets should be $2^{64}$.  Can somebody help?
26974
Okay, so I needed to find the smallest value of n such that algorithm 100*n^2 is faster than 2^n.   [what I have tried]  So, I instantly thought '0'. But, I then realized it can't be 0, 0 implies that there are no digits being entered in the algorithm, it also implies that the program does not run or terminate.   I typed in 2^32 and got a number over 4 billion. Okay, this is good, I'm finding numbers that have 100*n^2 being faster than 2^n.   I halved that, n = 20.  I kept inserting values counting down until I got to n = 15.   I also counted up from n = 10, the answer is undoubtedly n = 15, but I have a problem . . . .I solved this using brute force and that isn't good. What if I was given a bigger number and a larger bredth of numbers?  [What I need]  I need a way of finding the value instantaneously by only doing the math, I tried using logarithms, but my answer was wrong, my knowledge of logs is a bit rusty and I need a little help.  Think of it as a student trying to solve a question on an SAT or having a timer for a test.
9433
I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
101930
I have this algorithm and Im searching p and q:  $n=p^2 * q $  $l=(p-1)*(q-1) / \gcd (p-1,q-1)$  $d\equiv l^{-1} \pmod n$  And the values are:  For $n$:  1043247381320041410146374847683905608886067988802815759655490071506964811427733496668055364700822779908166748193534341903285387332658081562041534228961538451830025041762537639985150344917584064827615356535763872539925989984117068207555498700585376330731428359489791600319636079777025344217248475485835298689437926003958578141784379857951264973109214803916445702964047899447002191548965239884095802091798787988745415178578597206815122915438351636672681355517982410123569961242563194480399347961753678159210217993526738306796503660563163029287419732210247579793266891085178817047536758465239950861266592524206390869822972469137566045176690277813352563392838847417674529251627419479815097868890993153215515488877097760272399483111013602618554846096893805108827211344467797072352072430591318485091677011261912992157762106672216780766138057271434398274272110062768324672899209610001835423246735718435995420720133657793744810610657   for $d$:  105717877672224295784291675385546750129601472163379527375367128238003471793097341763391999503913659542087520808364287167645349555897774428176288829031477703594776341268160433668976237198330124904372546897953955241778475322074160469767162566234358907740412805211247598698481640207956827199048419949848619731050860757808082106844953602176503247786535423423104239566910713528691298692332149783689032722772009974404716783312200885555343877611094998117307970399241640213553820043460140493803404190774171912962651075100983834071259021038322886114660028788229094872545516054757700068264628024524394995795135464746570071201   How can I get $p$ and $q$?   Thanks!
39844
How would you write a non-recursive algorithm to compute n!?
24508
What would be the most optimal algorithm (performance-wise) to calculate the number of divisors of a given number?  It'll be great if you could provide pseudocode or a link to some example.  EDIT: All the answers have been very helpful, thank you. I'm implementing the Sieve of Atkin and then I'm going to use something similar to what Jonathan Leffler indicated. The link posted by Justin Bozonier has further information on what I wanted.
19952
I'm doing some research about time complexity of algorithms and stumbled upon the following problem that I'm not able to solve:  Let $T(n) = T(n/3) + T(2n/3) + 5n$. prove that $T(n) = O(n log n)$  First, I made a recursion tree, which is the same as the one in the question:   I found out that each level costs $5n$ and that the leaves have different depths (The left path is the shortest with height $log_3 n$ and the one on the right is the longest with height $log_{\frac{3}{2}}n$).  Now, since we need an upper bound, I took the longest path of height $log_{\frac{3}{2}}n$. This gives total costs $5n \cdot log_{\frac{3}{2}}n$.  Now I want to prove with induction on $n$ that this is true. I proceeded in the following way:  Assume as induction hypothesis that $T(k) \leqslant 5k \cdot log_{\frac{3}{2}}k$ for $k &lt; n$. Then:  $T(n) \leqslant T(n/3) + T(2n/3) + 5n$ $=^{IH} \frac{5}{3}n log_{\frac{3}{2}}(\frac{n}{3}) + \frac{10}{3}n log_{\frac{3}{2}}(\frac{2n}{3}) + 5n$ $= \frac{25}{3}n log_{\frac{3}{2}} n - \frac{5}{3}n log_{\frac{3}{2}} 3 - \frac{10}{3}n log_{\frac{3}{2}} 3 + 5n$ $= \frac{25}{3}n log_{\frac{3}{2}} - 5n log_{\frac{3}{2}} 3 + 5n$  And this is certainly not smaller then or equal to $5n \cdot log_{\frac{3}{2}}n$. I've spend an entire day now on solving this recurrence relation, but nothing solved it so far. Could you help me solving this problem?
70875
Context: I am learning Dijstra's Algorithm to find shortest path to any node, given the start node. Here, we can use Fibonnacci Heap as Priority Queue. Following is few lines of algorithm:  For each vertex in PriorityQueue{     do_something() }   If $V$ is the number of vertices, the subsequent lookup times in the priority queue will be: $$O(\log V), O(\log V-1), \ldots$$   Question:  What would the value of $O(\log V) + O(\log V-1) + O(\log V-2) + .. + O(\log 1)$?
68426
Given the radix-$r$ representation of a integer $n$, and a small integer constant $k$, there is an $O(\log n)$ algorithm for detecting whether $n$ is a multiple of $k$, namely, division, which produces as a byproduct the quotient $\lfloor n/k\rfloor$.  In general this is the best one can do. But for certain choices of $r$ and $k$, for example $r=10$ and $k=2$, there is an algorithm which answers the question much faster (constant time) without producing the quotient.  Given the radix-$r$ representation of a integer $n$, we can extract the integer square root $\lfloor\sqrt n\rfloor$ in something like $O(\log^3 n)$ time by doing binary search, which Joriki notes below can be improved to $O(\log^2 n)$ with a sufficiently clever implementation. This gives an $O(\log^2 n)$ algorithm for determining whether $n$ is a perfect square.  Is there a significantly faster algorithm which correctly decides whether $n$ is  perfect square, without also producing the square root? I suspect not, but I would be interested to see a proof.
86919
For a permutation on $n$ elements, what is the worst-case minimal number of transpositions that need to be multiplied to give the permutation? The transpositions do not need to be adjacent.
9898
Code like this often happens: l = [] while foo:     # baz     l.append(bar)     # qux  This is really slow if you're about to append thousands of elements to your list, as the list will have to be constantly resized to fit the new elements. In Java, you can create an ArrayList with an initial capacity. If you have some idea how big your list will be, this will be a lot more efficient. I understand that code like this can often be refactored into a list comprehension. If the for/while loop is very complicated, though, this is unfeasible. Is there an equivalent for us Python programmers?
93502
Find the asymptotic tight bound in  $$ T(n) = 4T\left(\frac{n}{2}\right) + n^{2}\log n. $$  where $ \log n= \log _{2}n $ and $T(1) = 1$.  I should solve this using all three common methods: iteration, master theorem and substitution.  It is highly likely that this kind of recurrence equation will be in my test in two days. Thank you very much in advance!
67560
I am stuck on the 4 th one.I have done the rest.I have found out the value of a_n.But not getting how to proceed for the 4 th one.