Welcome! Log In Create A New Profile

Advanced

review 3

Posted by aronl 
Announcements Last Post
Announcement : Programming Students at UNISA School of Computing 06/19/2019 02:01PM
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
review 3
September 15, 2008 08:56AM
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
avatar Re: review 3
September 15, 2008 03:30PM
Hello Lazarus.

In the second problem you have i=*2
Do you mean i*=2
avatar Re: review 3
September 17, 2008 07:34AM
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)
avatar Re: review 3
September 17, 2008 08:19AM
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.

Click here to login