# review 3

Posted by aronl
Announcements Last Post
: Programming Students at UNISA School of Computing 06/19/2019 02:01PM
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 review 3 September 15, 2008 08:56AM Registered: 14 years ago Posts: 88 Rating: 0
Provide the time complexity of the following code fragments. Explain your answers.

i) for (int i = 1; i<=n/2; i++)
for (int j = 1; j<=n; j++)
sum++;

ii) for (int i=1; i<=n; i=*2)
for (int i=1 ; i<=10 ; i++)
doIt() ;

where the efficiency of the algorithm doIt is in the order of O(n2 ).

regards
Lazarus Aron
 Re: review 3 September 15, 2008 03:30PM Registered: 11 years ago Posts: 423 Rating: 0
Hello Lazarus.

In the second problem you have i=*2
Do you mean i*=2
 Re: review 3 September 17, 2008 07:34AM Registered: 11 years ago Posts: 423 Rating: 0
i) for (int i = 1; i<=n/2; i++)
for (int j = 1; j<=n; j++)
sum++;

outer loop: 1 + ((n/2)+1) + n/2 time units = n+2 => O(n)
inner loop: 1 + n+1 + n time units 2n + 2 => O(n)

basic operation: sum++ (multiplication rule) => n*n => O(n2)
 Re: review 3 September 17, 2008 08:19AM Registered: 11 years ago Posts: 423 Rating: 0
ii) for (int i=1; i<=n; i*=2)
for (int i=1 ; i<=10 ; i++)
doIt() ;

where the efficiency of the algorithm doIt is in the order of O(n2).

outer loop: 1 + (log n) + (log n) time units => 2(log n) + 1 => O(log n)
inner loop: 1 + (10+1) + 10 time units => 22 => O(1)
doIt() => O(n2)

multiplication rule: n2 * 1 * (log n)
remove lower order terms leaves n2 => O(n2)
Sorry, only registered users may post in this forum.