1 find an expression for the number of calls to doSomething0

1) find an expression for the number of calls to doSomething0. 2) Then simplify with O-notation. 3) Then find the amount of space used (approximately, using O-notation). void foo int n) for (int i 03 i k 567; i++) for (int j 03 j ni j++) for (int k 0; k ji k++) doSomething(); void fu(int a) for (int i 03 i a.length 2 1++ something (a[i]); int n a. length while (n 1) do something n 23 void phoo (int n) if (n 1) doSomething(); return; phoo (n/10)

Solution

a) 1) 567*(n*(n+1)/2)
2) O(n^2)
3) O(1)

b) 1) (n/2)+log(2)n
2) O(n)
3) O(n) // the space for storing the array

c) 1) 1
2) O(1)
3) O(logn) //the function recurses logn times.

d) 1) log(10)n+1
2) O(logn)
3) O(logn) //the function recurses logn times.