CSCI672 – Space and Time Complexity Name: ________________________
Given the code fragments below, determine the space and time complexity for each.
1.
public static int Search(int[] data, int item)
{
int n = data.Length;
for (int i = 0; i
if (data[i] == item)
return i;
return -1;
}
Time Complexity: _____________
Space Complexity: _____________
2.
public static Bitmap sharpen(Bitmap image)
{
for (int i = 0; i
{
for (int j = 0; j
{
sharpenImage.SetPixel(i, j, result[i, j]);
}
}
return sharpenImage;
}
Time Complexity: _____________
Space Complexity: _____________
3.
public static void sort(int[] arr)
{
for (int write = 0; write
{
for (int sort = 0; sort
{
if (arr[sort] > arr[sort + 1])
{
temp = arr[sort + 1];
arr[sort + 1] = arr[sort];
arr[sort] = temp;
}
}
}
}
Time Complexity: _____________
Space Complexity: _____________
4.
static int Fibonacci(int n)
{
int first = 0, second = 1, result = 0;
if (n == 0) return 0;
if (n == 1) return 1;
for (int i = 2; i
{
result = first + second ;
first = second ;
second = result;
}
return result;
}
Time Complexity: _____________
Space Complexity: _____________
5.
double Calculate(long iteration)
{
double pi;
for (int i = 1; i
{
pi = ((4 / i) – (4 / i + 2));
i + 4;
}
Console.WriteLine(pi);
}
Time Complexity: _____________
Space Complexity: _____________
6.
private static LinkedList _list = new LinkedList();
public static LinkedListNode GetValue(int value)
{
LinkedListNode node = null;
if (_list.Contains(value) )
{
node = _list.Find(value);
}
return node;
}
Time Complexity: _____________
Space Complexity: _____________
7. Rewrite the code in question #6 to be more efficient in Time Complexity and justify your solution.
public static int Add(int a, int b)
{
int answer = a + b;
return answer;
}
Time Complexity: _____________
Space Complexity: _____________
8.
private static string _value = "Insert Some String Here";
public static int locate(char ch)
{
int loc = -1;
_value = _value.ToUpper();
if( _value.Contains(ch) )
{
loc = _value.IndexOf(ch);
}
return loc;
}
Time Complexity: _____________
Space Complexity: _____________
9. Can the code in question #8 be simplified? If so, explain how and provide the new time and space
complexity.
10. Write an algorithm (or a C# fragment) that demonstrates O(n3
) time complexity.

"Get 15% discount on your first 3 orders with us"
Use the following coupon
"FIRST15"

Order Now