1 votes 1 votes for ( i= 1; i<=n; i++) for(j=n/3: j<=2n; j=j+n/3) sum =sum+1; What will be O and θ for this Algorithms algorithms asymptotic-notation + – aka 53 asked Nov 23, 2017 aka 53 368 views answer comment Share Follow See 1 comment See all 1 1 comment reply joshi_nitish commented Nov 23, 2017 reply Follow Share it will be θ(n) and O(n) or O(n2) or O(n3) or O(nn), order can be anything >O(n) 1 votes 1 votes Please log in or register to add a comment.
2 votes 2 votes Outer loop will run for n times and inner loop will run for 6 times only (n/3, 2n/3, n, 4n/3, 5n/3, 2n) Hence average case $\Theta$(n) and worst case will be >=O(n) Ashwin Kulkarni answered Nov 23, 2017 Ashwin Kulkarni comment Share Follow See 1 comment See all 1 1 comment reply aka 53 commented Nov 24, 2017 reply Follow Share Can i know how you wrote 'theta' directly For theta we should first prove that O is equal to Ω 0 votes 0 votes Please log in or register to add a comment.