I'm trying to brush up on my big o calculations. If I have function that shifts all of the items to the right of 'i' 2 spaces I have a formula that looks something like:

```
(n -1) + (n - 2) + (n - 3) ... (n - n)
```

Where the first iteration I have to move (x-1) items, the second (x-2) items, and so on... the method:

```
int[] s = {1,2,3,4, , }
public static char[] moveStringDownTwoSpaces(char[] s){
for(int j = 0; j < s.length; j++){
for(int i = s.length-3; i > j; i--){
s[i+2] = s[i];
}
return s;
}
}
```

I know this is O(n^2), but I don't quite understand the math behind transforming this:

```
(n -1) + (n - 2) + (n - 3) ... (n - n)
```

into this

```
O(n^2)
```

In my mind if n = 5 (String is of length 5), I would have...

```
(5-1) + (5-2) + (5-3) + (5-4) + (5-5) = 5(5 - ???)
```

which is

```
(n-1) + (n-2) + (n-3) + (n-4) + (n-5) = n(n - ???)
```

so that gives me 5*5 = 25 which is n^2. but what is the ??? I don't know what to put for the variables in the formula. I don't even know if I'm even going by this the correct way. AKA I forgot how to do math :(

```
(n -1) + (n - 2) + (n - 3) ... (n - n)
```

Just rewrite the following as:

```
1 + 2 + 3 + ....+ (n-1)
```

which is equal to: `(n(n+1)/2 - n)`

.

Now you can see it is `O(n^2)`

.

As noted by @hvd you may want to put the `return`

statement outside the loop.

The Big-O notation is not the exact upper bound. It's an asymptotic upper bound. In many cases where a algorithm may look like O(n^2), but amortized analysis may show a linear order complexity.

Similar Questions

Somehow, sometimes, I'm ending up in a state like this : > x [1] 1 2 3 > get(x) Error in get(x) : object 'x' not found > x [1] 1 2 3 I can't reproduce it reliably. What sort of things mi

Are there huge differences in OpenGL 3.x vs 2.x? Is it waste of time learning OpenGL 2.x or are they both following the same concept? I think i read somewhere that 2.x was state based and that 3.x was

As the title says, is y = x = x + 1; undefined behavior in C?

HTML: <div id=foo></div> CSS: #foo { width: 100px; height: 100px; background: #f00; } .a { -webkit-transition: -webkit-transform 1s linear; -webkit-transform: translateY(100px); } .b {

is there any advantage to using this code double x; double square = pow(x,2); instead of this? double x; double square = x*x; I prefer x*x and looking at my implementation (Microsoft) I find no adva

I have (apply f '(x1 x2 x3 .... xn)), and I'd like to change it to a macro expansion: (f x1 x2 x3...xn). What kind of problems can occur?

I am working on a universal app with hundreds of background images. To save disk space and prevent further duplication and disk spamming I want to reuse the non-retina @1x iPad images as retina @2x iP

In x = x + 1, is x evaluated twice? If so, does that mean in x += 1, x is only evaluated once? How are the two expressions evaluated in terms of compiler intermediate code? For example, x++ could mea

Im not great in php and I could do with a little help. I want to say something like if ($x == 1 or 2 or 3 or 4) {do function} but the only way i know how to do that is to go if (($x == '1') or ($x ==

I need to read X11 source code, since there are a number of X11 versions, like: X11R1 X11R2 ... X11R7.7 how can I find out which version of X11 my ubuntu 10.04 has installed? thank you.

I am trying to solve this equation with 28 variables: y = (a1 * x1) + (a2 * x2) + .... + (a28 * x28) 1) y is known, so are a1, a2 all the way through a28. 2) x1, x2 ..... x28 are unknown variables a

bool? x = true; if (x == true) looks awkward. But sometimes that is exactly what is needed. Is there a better way? EDIT: Thank you all for the attempts, but so far I have not found a way that would b

What happens (behind the curtains) when this is executed? int x = 7; x = x++; That is, when a variable is post incrementednand assigned to itself in one statement? I compiled and executed this. x is

I am confused whether or not it is advisable to use x += 1 or x = x+1. I know that they both produce the same results. In practical terms, are there any performance gain when using x+=1 instead of x =

I have a question and is this: In CSS we use background-repeat: repeat-x (or repeat-y) for repeat an image along the page... so, in Android I can use something like that? I wanna use something like th

I had choosen Cocos2d v1.01rc instead of 2.x when starting developing my first game two months ago. Now that I am learning more I realized that ARC is fully supported and integrated in Cocos2d 2.x and

Does Tortoisegit work with PortableGit-x.x.x.x-previewyyyyyy? If yes, how to arrange these?

Can someone share a technique using MATLAB to plot the surface f(x,y)=(21/4)x^2y over the region x^2 <= y <= 1? Also, if anyone is aware of some tutorials or links that would help with this type

I'm creating a 1x1 Android widget. I have designed images for each screen density as follows: ldpi (120 DPI) = 72 * (120 / 160) == 54 x 54 pixels mdpi (160 DPI) = 72 * (160 / 160) == 72 x 72 pixels hd

I am currently reading a book about bit fiddling and the following formula appears: x-y = x+¬y+1 But this doesn't seem to work. Example: x = 0100 y = 0010 x-y = 0010 ¬y = 1101 ¬y+1 = 1110 x+1110 =

Consider the theory theory Scratch imports Main begin notepad begin fix P and f g h :: int ⇒ int assume prems: P f P g P h assume comp: ⋀ f g. P f ⟹ P g ⟹ P (λ x. f (g x)) have P (λ x. f (

I wrote this code: #include <cstdio> #include <queue> class Obj { bool x; public: Obj(): x(true) {} Obj(Obj&& o) { o.x = false; } ~Obj() { if(x) { std::puts(Here); std::printf(%

I am on a Windows machine running cygwin and X, with three monitors. When I ssh -Y to a remote machine, DISPLAY is set to something like localhost:15.0. Is there a way to determine what other values c

I need to plot set of equations: x1 + 2 * x2 == 8 x1 + 2 * x2 == 10 x1 == 5.5 x2 == 2.5 I am trying to use sympy for this: from sympy import * x1, x2 = symbols('x1 x2') plot( solve(Eq(x1 + 2 * x2, 8)

In this code x = [x for x in range(3)] global x is equal to [0, 1, 2]. The x in the list comprehension is a local variable. Then let's define x = [lambda: x for x in range(3)], what will x[0]() return

My professor recently said that although x = x + 1 and x++ will obviously give the same result, there is a difference in how they are implemented in the JVM. What does it mean? Isn't compiler like: he

Can i upgrade my elasticsearch just by moving the data folder from the elasticsearch-0.90.x folder to the elasticsearch-1.x.x folder, like this: curl -XPOST 'http://localhost:9200/_shutdown' ps ax | g

Let f[x_,y_,z_] := Sqrt[3x+1]+Sqrt[3y+1]+Sqrt[3z+1] I want to get the minimum of f for x>=0&&y>=0&&z>=0&&x+y+z==1 using mathematica. PS: I do know how to get the mini

I see it used in sorting, but what do the individual components of this line of code actually mean? key=lambda x: x[1] What's lambda, what is x:, why [1] in x[1] etc... Examples max(gs_clf.grid_score

Hello can somebody help me in expressing (x^3)/1000 - 100*x^2 - 100*x + 3 in big theta notation. It looks like of x^3 to me, but obviously at x = 0 obviously this polynomial gives a value of 3. Multip

Is there a way in magento to create a rule where after you buy X, each additional product you get 1/2 off?

I see some data format like \x{ff41} in my regex patterns. I know how to use it via some examples but don't know what it means in PHP.And now I need to figure out whether a character is included by a

I'm migrating from 3.x to 4.x and I'm running some queries to verify that everything works like before. I've found however that the query galaxy s3 is giving much less results. In 3.x numFound=1628,

How do I represent the following condition in a sql where clause? where id in Case x=0 then (1,2,3,4) case x=1 then (1,2) case x=2 then (3,4)

I copied some namespace data from x1 to x2 using remote api and lowlevel datastore api. I am accessing the x2 app, to get the following error for some data java.lang.IllegalArgumentException: app x1

I found some example source code where the author seems to use bitwise & operator instead of % operator. However when I tried x & 4 it doesn't produce the same value as x % 5.

Prove, using only the definition of O(), that 2^sqrt(x) is not O(x^10). I have been doing a few exercises on Big O and this is the first time I have encountered the variable in the exponent. I was won

I'm trying to solve the following problem: Given a 3x3 grid with numbers 1-9, for example: 2 8 3 1 4 5 7 9 6 I have to sort the grid by rotating a 2x2 subgrid clockwise or counter-clockwise. The abov

Design a function f such that: f(f(x)) == 1/x Where x is a 32 bit float Or how about Given a function f, find a function g such that f(x) == g(g(x)) See Also Interview question: f(f(n)) == -n

How to lock / stop drag .x? please help me. i want to make look like a scroll. sc_btn.addEventListener(MouseEvent.MOUSE_MOVE, fl_ClickToDrag_2); function fl_ClickToDrag_2(event:MouseEvent):void { sc

This executes as I'd expect: >>>x=[] >>>x.append(3) >>>x [3] Why does the following return None? >>>x = [].append(3) >>>x >>>

I am in progress of making my first 3D game, but I stuck into one part. I have never been good with algortihms or even math, so I am kinda having hard time with this :( Anyways, I want to generate 3x3

What is the equivalent of R's ecdf(x)(x) function in Python, in either numpy or scipy? Is ecdf(x)(x) basically the same as: import numpy as np def ecdf(x): # normalize X to sum to 1 x = x / np.sum(x)

Say I have two lists one longer than the other, x = [1,2,3,4,5,6,7,8] and y = [a,b,c] and I want to merge each element in y to every 3rd index in x so the resulting list z would look like: z = [1,2,a,

What's the best way to do movement in a 2D square grid system? I have this something that works but it seems wrong/ugly (see below). x x x x x x x x x x x x x x x x x O x x x x x x U x x x x x x x x x

i want to get the negative number out of x mod -3 in Java. e.g.: 1 mod -3 = -2 or 2 mod -3 = -1 Is there any method for this problem?

I am writing an AR application on iOS and am using CATransform3D transforms on a UIView. Through OpenCV, I can get a perspective matrix through the call cvGetPerspectiveTransform(). This returns a 3x3

I have the string x61y78 for example. How can I divide it into strings var x=61; and var y=78; using javascript? I tried using for loops and splits but I got weird results and though there should be a

This question already has an answer here: Does range() really create lists? 3 answers I was looking at the range function and an online search shows that (EDIT: in 2.x) it's eagerly evaluated &

I have some specific id like 1,2,5,11,64589 in solr (int type) I want to qet query like ttp://localhost:8983/solr/select?q=x:[1,2,5,11,64589] but does not work (get error). how can do it ??? Note: i