门外汉，求助算法分析与设计基础题解答，拜托各位！
各位仁兄仁姐，小妹没学过数据结构，被迫帮别人要做几道题，在网上查了半天还有6道没有解决。无奈时间有限，自己现学已来不及，不过感觉应该是些基础的，或者某些课本的原题。请知情者指点迷津，不胜感激！！先将原题粘上，希望学过的朋友，指点一下！
1.用Step Table的方法计算下面算法的时间复杂性
template <class T>
void Insert(T a[],int & n,const T& x)
{//Insert x into the sorted array a[0:n-1].
//Assume a is of size > n.
int i;
for (i = n-1;i >= 0 && x < a[i]; i--)
a[i+1] = a[i];
a[i+1] = x;
n++; //one element added to a
}
解：
2.证明下面的渐进表达式成立
E4：
I2：
解：
3．分别用迭代展开和Master方法计算下面递归关系的复杂性
解：
4．考虑 而不是 的连续背包问题。一种可行的贪婪策略是：按价值密度非递减的顺序检查物品，若剩余容量能容下正在考察的物品，将其状如；否则，往背包中装入此物品的一部分。
1）对于n=3，w=[100,10,10], p=[20,15,15]及c=105，上述装入方法获得的结果是什么？
2）证明这种贪婪算法总能获得最优解。
解：
5．使用2-优化方法求解以下0/1背包问题的实例并给出求解过程。n=4,c=20,w=(10,15,6,9),p=(2,5,8,1)
6．给出快速排序的非递归算法，要求堆栈中只需保存left和right中较小者的边界。证明所需要的栈空间大小为 。
