C++, 136

template<int N>void rotate(int(&a)[N],int k){auto r=[](int*b,int*e){for(int t;--e>b;t=*b,*b++=*e,*e=t);};r(a,a+k);r(a+k,a+N);r(a,a+N);}

def r(a,n): return a[n:]+a[:n]

Could someone please check if this actually meets the requirements? I think it does, but it I haven't studied CS (yet).

JavaScript 45

Went for golf anyway because I like golf. It is at maximum O(N) as long as t is <= size of the array.

function r(o,t){for(;t--;)o.unshift(o.pop())}

To handle t of any proportion in O(N) the following can be used (weighing in at 58 characters):

function r(o,t){for(i=t%o.length;i--;)o.unshift(o.pop())}

Doesn't return, edits the array in place.

Python 2, 57

def rotate(l,n):
 return l[len(l)-n:len(l)]+l[0:len(l)-n]

If only l[-n:len(l)-n] worked like I'd expect it to. It just returns [] for some reason.

APL (4)

¯A⌽B

• A is the number of places to rotate
• B is the name of the array to be rotated

I'm not sure if APL actually required it, but in the implementation I've seen (the internals of) this would take time proportional to A, and constant memory.

I don't see very many C++ solutions here, so I figured I'd try this one since it doesn't count characters.

This is true "in-place" rotation, so uses 0 extra space (except technically swap and 3 ints) and since the loop is exactly N, also fulfills the O(N) complexity.

template <class T, size_t N>
void rot(std::array<T,N>& x, int shift)
{
        size_t base=0;
        size_t cur=0; 
        for (int i = 0; i < N; ++i)
        {
                cur=(cur+shift)%N; // figure out where we are going
                if (cur==base)     // exact multiple so we have to hit the mods when we wrap
                {
                        cur++;
                        base++;
                }
                std::swap(x.at(base), x.at(cur)); // use x[base] as holding area
        }
}

C (118)

Probably was a bit too lenient with some of the specifications. Uses memory proportional to shift % length. Also able to rotate in the opposite direction if a negative shift value is passed.

r(int *a,int l,int s){s=s%l<0?s%l+l:s%l;int *t=malloc(4*s);memcpy(t,a+l-s,4*s);memcpy(a+s,a,4*(l-s));memcpy(a,t,4*s);}

Factor has a built-in type for rotatable arrays, <circular>, so this is actually a O(1) operation:

: rotate ( circ n -- )
    neg swap change-circular-start ;

IN: 1 9 [a,b] <circular> dup 6 rotate >array .
{ 4 5 6 7 8 9 1 2 3 }
IN: 1 9 [a,b] <circular> dup 3 rotate >array .
{ 7 8 9 1 2 3 4 5 6 }

A less cheatish Factor equivalent of Ben Voigt's impressive C solution:

: rotate ( n s -- ) 
    reverse! swap cut-slice [ reverse! ] bi@ 2drop ;

IN: 7 V{ 0 1 2 3 4 5 6 7 8 9 } [ rotate ] keep .
V{ 3 4 5 6 7 8 9 0 1 2 }

Java

public static void rotate(int[] arr, int by) {
    int n = arr.length;
    int i = 0;
    int j = 0;
    while (i < n) {
        int k = j;
        int value = arr[k];
        do {
            k = (k + by) % n;
            int tmp = arr[k];
            arr[k] = value;
            value = tmp;
            i++;
        } while (k != j);
        j++;
    }
}

Demo here.

Minified Javascript, 114:

function rotate(e,r){n=e.length;i=0;j=0;while(i<n){k=j;v=e[k];do{k=(k+r)%n;t=e[k];e[k]=v;v=t;i++}while(k!=j);j++}}

Python 3

from fractions import gcd
def rotatelist(arr, m):
    n = len(arr)
    m = (-m) % n # Delete this line to change rotation direction
    for i0 in range(gcd(m, n)):
        temp = arr[i0]
        i, j = i0, (i0 + m) % n
        while j != i0:
            arr[i] = arr[j]
            i, j = j, (j + m) % n
            arr[i] = temp

Constant memory
O(n) time complexity

Ruby

def rotate(arr, n)
  arr.tap{ (n % arr.size).times { arr.unshift(arr.pop) } }  
end

vb.net O(n) (not Constant memory)

Function Rotate(Of T)(a() As T, r As Integer ) As T()     
  Dim p = a.Length-r
  Return a.Skip(p).Concat(a.Take(p)).ToArray
End Function

C (137 characters)

#include <stdio.h>

void rotate(int * array, int n, int k) {
    int todo = (1<<n+1)-1;
    int i = 0, j;
    int tmp = array[0];

    while (todo) {
        if (todo & 1<<i) {
            j = (i-k+n)%n;
            array[i] = todo & 1<<j ? array[j] : tmp;
            todo -= 1<<i;
            i = j;
        } else tmp = array[++i];
    }
}

int main() {
    int a[] = {1,2,3,4,5,6,7,8,9};
    rotate(a, 9, 4);
    for (int i=0; i<9;i++) printf("%d ", a[i]);
    printf("\n");
}

Function rotate minified to 137 characters:

void r(int*a,int n,int k){int m=(1<<n+1)-1,i=0,j,t=a[0];while(m)if(m&1<<i){j=(i-k+n)%n;a[i]=(m&1<<j)?a[j]:t;m-=1<<i;i=j;}else t=a[++i];}

python

   import copy
    def rotate(a, r):
        c=copy.copy(a);b=[]
        for i in range(len(a)-r):   b.append(a[r+i]);c.pop();return b+c

C

Not sure what the criteria is, but since I had fun with the algorithm, here is my entry:

void rotate(int* b, int size, int shift)
{
    int *done;
    int *p;
    int i;
    int saved;
    int c;

    p = b;
    done = p;
    saved = *p;
    for (i = 0; i < size; ++i) {
        c = saved;
        p += shift;
        if (p >= b+size) p -= size;
        saved = *p;
        *p = c;
        if (p == done) {
            p += 1;
            done = p;
            saved = *p;
        }
    }
}

I'll golf it for a good measure too; 126 bytes, can be made shorter:

void r(int*b,int s,int n){int*d,*p,i,t,c;d=p=b;t=*p;for(i=0;i<s;++i){c=t;p+=n;if(p>=b+s)p-=s;t=*p;*p=c;if(p==d){d=++p;t=*p;}}}

REBEL - 22

/_(( \d+)+)( \d+)/$3$1

Input: k expressed as a unary integer using _ as a digit, followed by a space, then a space-delimited array of integers.

Output: A space, then the array rotated.

Example:

___ 1 2 3 4 5/_(( \d+)+)( \d+)/$3$1

Final state:

 3 4 5 1 2

Explanation:

At each iteration, it replaces one _ and an array [array] + tail with tail + [array].

Example:

___ 1 2 3 4 5
__ 5 1 2 3 4
_ 4 5 1 2 3
 3 4 5 1 2

Here is a long winded C version of Colin's idea.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
  int t;
  if (a < b) {
    t = b; b = a; a = t;
  }
  while (b != 0) {
    t = a%b;
    a = b;
    b = t;
  }
  return a;
}

double arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int s_arr = sizeof(arr)/sizeof(double);

/* We assume 1 <= by < s_arr */
void rotate(double *arr, int s_arr, int by) {
  int i, j, f;
  int g = gcd(s_arr,by);
  int n = s_arr/g;
  double t_in, t_out;

  for (i=0; i<g; i++) {
    f = i;
    t_in = arr[f + s_arr - by];
    for (j=0; j<n; j++) {
      t_out = arr[f];
      arr[f] = t_in;
      f = (f + by) % s_arr;
      t_in = t_out;
    }
  }
}

void print_arr(double *arr, int s_arr) {
  int i;
  for (i=0; i<s_arr; i++) printf("%g ",arr[i]);
  puts("");
}

int main() {
  double *temp_arr = malloc(sizeof(arr));
  int i;

  for (i=1; i<s_arr; i++) {
    memcpy(temp_arr, arr, sizeof(arr));
    rotate(temp_arr, s_arr, i);
    print_arr(temp_arr, s_arr);
  }
}

If you perform each of the possible cycles of rotations by n in turn (there are GCD(n, len(arr)) of these), then you only need a single temporary copy of an array element and a few state variables. Like this, in Python:

from fractions import gcd

def rotate(arr, n):
    total = len(arr)
    cycles = gcd(n, total)
    for start in range(0, cycles):
        cycle = [i % total for i in range(start, abs(n * total) / cycles, n)]
        stash = arr[cycle[-1]]
        for j in reversed(range(1, len(cycle))):
            arr[cycle[j]] = arr[cycle[j - 1]]
        arr[cycle[0]] = stash

Python

def rotate(a, n): a[:n], a[n:] = a[-n:], a[:-n]