CSCE 222 Lecture 3

« previous | Monday, January 24, 2011 | next »

Intro to Ruby

Elementary Operations

• assignment ( = )
• arithmetic ( + - * / % )
• boolean operations ( && || & | ^ ! )
• comparisons ( < <= == >= > )
• indexed (array) access ( [i] )

All have constant running time, i.e. $\mathrm{\Theta }(1)$ time.

Statements

block 1 { }
block 2 { }
block 3 { }
# ...
block k { }

If block k takes $T_1$ time, then $T=T_1+T_2+T_3+...+T_k$ to execute all blocks.

Control Structures

if BoolExpr then
  block 1 { }
else
  block 2 { }
end

If evaluation of BoolExpr takes $T_B$ time and execution of block k takes $T_K$ time, then $T=O(T_B)+O(\max (T_1,T_2))$ to execute if statement.

For Loop

for k in (a..b) do
  block 1 { }
end

If block 1 takes $T_1(k)$ time, then $T=O(T_1(a))+O(T_1(a+1))+...+O(T_1(b))$ for entire for statement.

Function calls

def f( params )
  block 1 { }
end

If $T_P$ is time to assign parameters and $T_1(params)$ is the time to execute block 1 given params, then $T=O(T_P+T_1)$ for function call.

Example

def bubble_sort(list)      # O(1) params
  list = list.dup      # O(n)
  for i in 0..(list.length - 2) do      # O(n^2) (runs (O(n) n times)
    for j in 0..(list.length - i - 2) do      # O(n) (runs O(1) n times)
      list[j], list[j+1] = list[j+1], list[j] if list[j+1] < list[j]      # O(1)
    end
  end
  return list      # O(!)
end  # O(1) + O(n) + O(n^2) + O(n) + O(1) = O(n^2)